7050 785 856351245 833110803 993793973 593936313 836091734 401370256 854967653 751756651 616422227 475123263 873036431 957068482 855181514 562852884 380099467 935034863 278802980 506280965 745092668 655112779 939121082 870847912 944585490 615904169 685932850 469348387 482668387 372839320 930611129 604510272 931736015 149172992 665624833 484065976 463236297 629486258 321286732 660004486 901695731 670034402 734640126 632051095 712248588 681590742 942109187 616628097 902599182 934390316 996235052 285808367 542708262 718634172 582663085 500423390 648871415 831115163 630935552 756121956 404526362 581401263 635017850 864862198 840541441 494965083 971262750 656980812 931770708 289323472 837557556 571915156 912547090 866057379 249696264 900378637 841984977 702797597 764589323 741752966 892804931 943724226 704450018 337457185 499798136 823340887 584023002 697420709 393016510 982867845 721339178 784909263 961817788 816256985 511184556 605232687 126009626 951002694 998611502 351666754 990763244 623904356 790260916 948815668 973010536 626235480 954672059 695612062 856751533 327246337 597367722 540570275 929842655 993853192 946563999 934128635 606819969 857361404 908386472 902887601 972995480 606095525 798217285 641645864 811036824 650111644 431361393 471069421 782556303 875146889 491418638 766757714 651439975 727113560 234496524 839017826 694135980 974843259 631018220 775514719 491011266 363754844 883293788 581186411 280550005 583115729 716628589 889418212 306105071 226325234 963353433 741579905 835052827 671660228 890649954 789075671 723118119 873484575 713588786 848287285 398023435 817330578 865335123 888470187 688195237 911638055 853873584 341882518 890828059 665680868 997112654 720919936 818676713 985253086 354029897 361092322 842799774 904958620 436672697 755230950 934801321 605273744 451288388 740768576 480228424 360371137 902331487 439023879 368433636 476014881 998564444 453788265 107426064 736149354 913807800 820387660 958677688 362220952 707543896 359149779 565333855 411020818 894815206 735431935 378720704 982348914 977567591 646090588 963912628 872880843 834181339 754604779 628769675 551955768 448528978 413963714 483939813 320101181 979955673 252923716 666120319 844203146 740824094 997929671 256839592 974025068 771586459 918046611 988493494 724360901 782674239 592936175 61136898 440096670 768651612 189913828 766668766 958974393 853827583 485749136 164275276 979254232 950398171 894748266 597518154 123423293 822781965 657494143 501993620 473072627 766826422 636670113 864838139 835492359 347920000 680891355 787128741 802989429 440086879 713290627 411821312 871038980 233937064 299403182 913182317 711241547 794810137 844704463 617404012 491234834 880704255 950144327 278279422 523877304 778472289 700339426 837059340 511594166 531457592 932400432 899567637 834358546 865396106 922130938 761368231 859049994 840775058 426754963 165087675 956303704 978361400 837550753 619492871 516707769 747636495 700253647 899750345 364916258 805234280 702052241 379945139 208850140 878268880 778901250 869980698 871734794 858909658 249775374 444643163 650043788 954281324 387438712 305894189 770392746 889575196 761700124 775378891 693912881 495566896 737422037 969657404 875811145 676553059 835021927 952157681 582718704 397308454 856787683 980788637 828750321 766391037 712421052 732187637 921879758 673714934 363041328 650532212 821078368 860731898 909970322 660643463 935438353 917129503 286060265 156773648 638907614 764141585 529542889 559930829 336930144 591046575 613060836 762397613 975644320 940362495 977476325 874310957 584472328 608828527 889257456 514696813 470909062 675745056 912230002 727763904 921361237 999714368 350358207 614582522 311622299 908139323 878939132 512320054 235407684 683847726 479076207 931718451 549913049 403089308 745086991 995313173 617830466 518357645 678072025 144277773 723278126 717620829 671603385 898923661 809791413 818761256 797642854 843781193 492604895 886100549 988816262 455890205 881173975 117791160 967746190 129187007 681219015 695043917 597766605 206795173 402009031 784101594 995045348 980931585 489565360 477650971 877372576 394215858 70250018 278039695 429073106 715120366 966444154 987731617 742106558 417822119 384262459 676434858 906950606 636236284 845205024 622802877 814025955 878120295 331479497 405254370 464713425 730359558 961687758 805125671 547578902 542475661 424164253 889396627 946291060 551760632 900583239 836104500 754613613 801400010 750183599 569336495 701247225 798534233 966620977 842023630 314191844 936556851 670224547 883221321 815011475 939943539 742781450 825622818 148919848 819915954 834604885 962507279 765353042 840762982 332696899 770155999 836079778 965656186 533298309 221947382 819456718 979995809 644531532 753268637 775193566 405026664 782762890 482580896 937176989 709773032 932789295 832702214 168067539 715317004 784833537 435056618 643990437 891998936 683073869 183152051 827101103 950110050 201744246 331396374 748326950 534526144 464299843 253379044 224702509 582630861 737116407 236909396 231455138 971080541 711206583 934057850 486792644 798537019 896871116 737430157 680332796 406728246 930957411 605427445 511676149 771571331 542070238 669057222 922161234 960024931 800851575 260905193 540854518 628865673 928893387 948264200 737413105 618316914 859510072 765752646 533087335 954900627 754930942 893894828 629934957 713871671 939650110 567286654 692102089 418411210 218683878 889837903 349582381 636312942 63600595 909321291 768763491 796667332 992281230 673625810 715283991 801062320 241691585 950216794 883192282 491483841 650946773 643747466 578075384 466465542 944664807 972823950 490815911 910114900 548958466 652616933 571018804 186611016 392392194 215652816 455934162 688542882 969528390 542740641 744894306 664266600 967183409 539617868 993393971 884054327 219877979 971547724 502251237 270267958 525120115 778953638 676073434 216691533 310256735 393141284 267719633 124588878 296925225 774433893 268202713 51678993 957264924 900994549 203633714 689517765 282604531 549716449 329032730 751050903 735668252 911455548 875578844 553728384 235468851 743872431 560099215 866614219 49853787 995237195 490927343 830583510 207773165 692759117 857160689 640100396 456012804 820409000 227990724 905433586 708421501 240892476 892422762 892559547 369903754 651504950 992417075 624290695 699389503 910155268 185066912 228823489 818937752 692490326 322582512 326801208 672459879 789690927 532448840 927562462 432354434 891195018 970690931 819997253 625363890 117612588 407505319 810834449 813648149 883545262 485420166 599087838 574149470 789694625 640246639 454533068 618258719 685544745 584358593 719517825 665352689 873103359 502694676 759826016 784616591 907747887 732512053 135670710 771491074 524150290 82363340 970344702 492418111 142730969 608880019 936768920 259840730 382558399 888617979 574233458 806596499 305378936 956380690 884307575 956709695 663435398 383829069 279795808 981585869 193027405 939898704 795705374 241045555 714997753 936997332 920726671 854326535 921118117 619574925 992178782 261399654 382701043 936504525 852115729 612361273 831284626 900483801 566067226 701267405 876595191 951911469 537105780 551883192 718337901 633094355 822925506 534049962 540710590 639158115 775743370 651218695 583975472 939215282 152518889 563351025 757734195 528763559 824432349 521118108 795740531 931601463 851964161 311877657 689348427 583384858 387171246 611149151 434362556 655039782 763637992 947709274 985997319 870737823 521613846 919940627 753679284 684530964 945935724 850007322 699019607 635973907 952948676 689667140 630864903 353252668 619382750 817549199 149830063 467233905 981516375 967230187 269643719 929333915 375670538 701825658 905360948 825765047 435396356 909731202 319277344 792425498 957933390 363202798 525528243 248969223 834235871 943046737 600758158 983962555 904345154 976945335 577538704 999468729 476667129 858994941 767019628 741129678 972850625 679039785 753800811 996739680 847369253 299786874 440312045 807324273 894843239 615608407 728184274 445564671 810954179 973559746 561629205 785927581 381681397 202094145 831217566 776080740 904916284 678472876 688741420 965046921 585033083 408673537 976145058 67600335 781786326 961696592 549386767 684353361 673826424 672586870 577698250 801872502 653499619 807298907 374898159 468970514 709120056 480620691 667083531 964972351 484116927 833010344 866772259 488765104 646359164 849585865 594017770 591528228 870575435 581408256 606078281 82331737 939077743 877457621 713925230 767076773 693666406 889637339 891144715 893465978 306452386 498078867 759248096 265208394 494123057 383674251 910322952 120607107 278267234 846350882 827720410 320001093 888781270 897291885 383290897 884472208 738585970 598575290 434976783 306658212 984487327 479439814 945301342 236043412 984590367 455067405 410148314 927017488 735079665 479075440 930111518 479919156 781379526 763732393 506618143 982481315 382280156 792195588 603374771 503924381 328957709 640594636 984584878 957831943 594962892 533556529 336046109 890367406 649973165 193387207 893598489 814862005 655960480 808427065 695960256 590245580 568897232 820859241 533065949 917152404 646071991 952386474 487593049 866699407 863234591 566425284 586827115 590333613 986477441 308784618 393106338 433378603 833294212 808189718 997309325 499760687 860054746 628564651 871803718 763442818 878099650 958747220 953210143 378996866 479864374 903579009 675261583 704506604 943547419 633294637 910907571 609664051 705469040 786573860 801286821 281613367 166533049 996320560 414704023 745901118 816131237 737055523 743746490 287494095 755703630 883192299 955136088 639002863 327577122 556075630 900002043 98344397 566710111 465256081 621535479 507853680 608608007 592618350 811219956 958791621 108733690 958921676 823421810 649661382 682636163 506338658 725892401 503952889 764877511 750594744 816614266 58278443 849447790 509351042 954754907 845496484 261518155 688612344 976054834 963629808 789015140 625475731 264112790 878660475 767292386 762226847 919345223 944012134 977497525 73073359 236167836 903025717 930579124 963263758 559122531 785980685 979042276 854522069 418299255 915217757 849201215 820666893 769899697 951992720 536533448 262116336 330334549 881372016 883275018 747226008 419414544 924304724 829335962 514740676 857135367 808560859 891985011 562117674 878523921 512883410 888840781 571194206 418941709 761646774 512196885 713748281 940077851 895857279 791536044 428689549 799601702 985300895 392938266 981587613 651154335 795124890 941672199 617458830 935800099 651238630 639161363 852630811 454289651 505113322 782087006 285026207 842365970 902227796 949690145 768715636 751196598 818631802 983224434 736834924 713260484 112112581 713961451 889815125 899821162 649647703 253192648 841032201 719980160 287417328 935027984 849695169 843514775 589840281 603771746 612312512 354382048 204495258 251975335 671842025 589438216 452338797 334948208 829321983 768879809 931089569 649983937 880755295 757003174 614895819 816975108 757697221 766001609 732062439 814599465 506607945 851332084 991997635 925638018 941099416 855952533 345731805 731807751 896186048 102746161 962842135 688660709 909470042 872942741 612806799 762199484 875358542 151556562 481408436 399097422 774163319 139897961 327791351 686896389 982945975 812213612 960651490 849698774 644329285 552057109 270738710 840923963 999693094 404957005 744570514 551811722 206412703 467692556 960521988 751147329 992820634 891224201 164512291 422583299 936980895 830110652 918546455 745001869 899940509 757695522 600305113 910160381 836578565 739210831 790586229 945742849 713974360 774569814 757637119 981580420 518418937 995474171 528463783 972063774 365681598 735261723 206114525 116453595 527926080 629097314 313670330 707721727 571647334 852089979 771164082 828417324 486898535 318144503 340634449 558144829 973924883 961230381 879988899 713121857 565198665 311970677 347984461 277039269 725670017 84076118 797429541 453129390 813668086 640426568 755428638 743760702 980049335 886116157 479984171 873265348 537275597 972927145 957825397 410981295 913266621 457101440 946895232 993424482 436289276 840212766 557218536 951015895 259815799 297597108 763916561 408992685 763993100 338450132 851641917 697303188 800015518 998271835 912687105 514902974 483077974 322218632 428185468 673032688 597520575 723604561 661321774 271394919 951675105 834527174 851825252 786904859 993592491 741630125 271513233 880684919 148963705 625594044 741982453 986989166 856764662 211199698 723321300 212904447 798710089 714870471 158530630 465632963 811839525 412466793 738915388 592592935 845896798 679599065 552653215 358766174 530899529 990574436 780538588 759868775 508547332 424517204 609682561 445499152 318492045 615179038 809997172 837563109 933617782 925051339 901388361 893811925 516507968 859532056 592139805 734306174 656813837 855315054 852610997 797504973 968801043 721964857 425375363 389225802 580712394 463790938 985336894 771168752 896568550 918662130 652009345 720956055 708660010 433896024 404561526 351605770 470789222 568189918 341462480 827767159 893099960 973744903 995081958 553049309 795695223 826048466 812764824 799449296 780157540 576577061 589820647 995192482 852405292 500566114 568531785 683582873 777614383 660512964 844902831 547550854 812441325 770152621 920275808 714919025 750044995 917109061 345526942 893655924 435243772 706227288 320171816 472747164 454928427 521350515 457242816 541397759 550332126 176725389 771277713 498746566 569153014 995445578 612110568 672358206 497417641 975738433 234778507 293922930 543019054 998971150 478761193 225729805 667126544 625553200 665428167 772316382 975689688 725672328 883183943 844627273 835736598 989312609 603220794 473407177 859475051 847798254 972176261 737205807 813243538 249972666 931840535 804641186 598628464 878264365 586519468 738963059 868754464 886965213 948148544 843888921 774632222 722425746 733624314 463393914 811590444 749285375 456534198 517087076 462762306 425392206 739109438 563490897 972188233 765499274 620756878 954370361 533402438 903711545 886454611 579587683 377963492 585840263 980355101 74111219 576926702 672649370 891397033 948829714 765336564 276585141 995662955 726864051 264088961 803696152 696367596 466474711 816624163 671089108 602730561 877407889 673354508 440535734 423818803 381930235 860325214 964158939 555757506 529709846 538060802 933368558 915874980 165757656 960550515 696906247 976817946 827204593 286483593 315936380 717003984 858213999 768346177 934330316 104859492 538392837 391992941 757228231 613163460 735926794 899350495 859465693 729536196 348410580 224817372 817416469 209372338 168776978 676084140 245167143 599096072 472703899 501846091 917197245 581977871 843186144 422846313 821719209 922176413 258437872 645766008 963496695 480425603 984165004 868531858 921883970 874706459 781068666 676026727 874637737 946492873 891412354 446481866 599286597 443952348 697175811 687225616 740096986 460816714 993673057 490921650 159079773 674817422 748476813 691788618 760277822 601743865 884944709 919445863 970088252 985262866 858438159 380517013 896364359 463397256 117078093 867145519 631887218 779644839 511374050 873433964 845048411 178143728 635490586 716472465 516889716 868960703 131989736 857911690 415048588 707187893 893811682 319790918 864556209 602717887 871637759 873202898 257874970 885364462 885066647 509138356 262721960 918395768 811258886 869764208 543483982 373988619 861960177 868798191 744252372 431679211 963460857 399266741 382347981 785639584 359091395 711702358 510201623 362026125 787481952 992715771 776297510 477712948 426217557 785828048 903717514 149856247 626490463 508738581 339615897 572782056 430069499 458017430 121908689 647608756 829618028 950778461 898809784 728724297 706108408 898608287 760255142 973859789 988654121 679929729 470050620 667867162 287321556 473655087 420400384 692495333 954490583 896994331 667272941 702600801 560379844 958127959 681516124 706354775 593625440 767747732 320208972 666727635 409250929 932935659 852538532 898325993 390064587 850273537 785369640 224546603 465241168 515431562 830182866 564429089 958384697 574562842 477754062 914614074 507088830 317122874 373896051 687659349 115974329 483386223 124103866 929658271 884010404 348598027 524288380 162036219 884756877 819541786 862214396 754791955 554225485 846830185 855897893 347280055 795947439 614391797 850912186 709389774 555304035 848953956 565289309 675572384 681311638 817695743 280105274 740337971 961524033 873104364 508050234 234867092 694779065 888958733 676124016 708059792 732366035 622039332 613227960 880766839 485116061 383867754 381773978 881900561 815955182 285009102 118128076 610065544 291404857 783483482 931043449 359300297 635694335 760360021 462071899 490938683 732554153 514696690 538360671 710433035 576836838 808475167 670156915 407465121 617099706 664373092 357073600 901886612 331901865 923896495 355506146 551991476 685592085 683152941 639695965 946175719 848479376 927573905 822603652 732045606 572855231 959859351 633592300 443011904 769106559 488950241 749010979 417629722 799426715 673464457 920284433 715274290 927710143 695372485 883186576 908125939 649193350 466178590 838750167 671851362 878794716 847594303 406729917 318497757 836828912 472601246 961456866 916705365 307915425 392386750 818209878 343629824 289125610 656702867 270190855 804614632 519951982 569062706 883708518 742183622 349440999 787793860 399676735 836345954 831607069 375163569 934183865 966523947 298996798 720886241 816073663 214134332 304013416 962222897 955918019 674357414 993836409 686377141 830763906 841434473 608331933 983947738 536935815 200347321 57543827 954824923 798776038 556755848 661189301 808637641 830673933 795362228 466282709 924576135 543036636 878315186 535524878 559612903 923920201 727892445 706782996 507889578 619730921 965187531 615497801 928386761 280280715 973860383 942039336 680049177 991202847 739099857 841125794 200375673 850757244 672138497 910234663 882217421 111163114 522782014 922421629 619220805 298833497 642185244 660387676 605666890 487607266 796536022 851997974 525669146 766593869 549204046 983741910 299213451 879646457 790917532 985933020 922825483 795151082 651901033 957827635 471600697 302360629 81008017 243386287 678603972 897061483 874420345 498991050 552461981 804904883 949927630 619921433 648235913 854857675 148065396 497740470 360074091 755902407 562580985 995002991 428625882 758204569 687351973 743314042 759727862 527238340 134980958 158825880 639551753 904306507 107321069 391449744 163383493 708283900 933578623 954462358 653188689 368510372 580659589 104356910 971039400 945767512 994067507 271201787 897550435 695793571 195061882 326347085 179582374 529347915 587133745 791898259 803931367 866642719 847774009 694275586 836394317 31301019 324822641 659176030 710750376 817389061 943209714 919682066 729959545 523738056 512020908 543732527 709033289 798166901 407978425 614138286 715753691 946495976 484099269 681736399 829857144 822735619 650150642 986372872 796517534 767152946 396776487 849542307 413557431 784199837 870331675 900556418 703944113 641917253 351324089 747607669 627111724 968324276 933610083 953606790 294845122 562949935 566898776 823053534 736359109 735247915 301884792 616659371 450677508 435061094 957524782 933104606 536630673 812877123 594582408 421356973 797811957 695140889 306057064 792797939 865679911 507352337 978950651 273923662 900782062 423413424 647826797 639471173 431584960 748368208 899448959 539455239 827754569 858158601 959773494 334161240 254760591 798646595 974017380 918976839 469841282 379788519 694543989 855766996 448665122 835297114 787035584 602470356 827838698 786468472 949866894 742491687 879908367 552028916 844565662 998741926 671835621 813471400 970977025 581519531 880725611 651961723 756284349 804629868 646331017 246177703 803449993 571777877 891412639 634206969 823425918 903410128 317972705 639703296 701485099 555475920 715354966 430731072 743766064 574030474 720300578 650255501 500034334 525966782 716394732 563616315 943854300 540803126 929764938 705281812 830196444 774286036 401636862 447962390 895314032 832014014 664343984 533875904 846332931 526013345 530216109 593816985 193033099 409775693 598537194 25359776 90391980 827078589 493062987 792481194 690437581 988211007 474674787 924012711 782302501 877644706 711606624 302140935 363199594 581509305 690574896 806873901 284192149 973296485 936961567 511909468 637738607 936358630 964100596 833586438 618276439 224869033 299557835 622380429 448297598 910769679 571206069 686651759 367655600 818374950 924273471 349078174 544748511 580628414 899480145 645176239 952781273 990658325 667536189 986079891 487179197 895181902 384817767 445879628 633391764 799245904 657297031 390573953 591717554 331656773 985509901 638124501 802461948 946266315 846818480 800396169 361842049 492959199 673788673 997820656 631625121 458610922 483722413 883093674 672959269 329948601 928438592 878344444 947895418 984991927 733486119 567750795 872032709 546005468 886711526 276226305 604686550 815620584 289246581 887840958 559020163 729718636 906935696 854318811 987005719 563021583 291287443 571715009 347820169 324439531 936379488 870188678 997810333 520510081 864620841 970501858 916939441 907031330 321246445 653525250 750366305 789493256 623791441 648353160 920872449 393468600 300503133 626144931 971587125 496487015 630269873 150158581 442579476 923524747 449022309 748370698 271958678 184380865 670292336 815467076 666197575 860587619 408950612 763107907 929482752 900663176 361798421 259745525 643646382 696948313 416012711 650346524 644570611 481742417 795907066 700170846 614286907 794365073 960327102 590825179 235715548 650858057 632277833 309644881 156842986 804442966 700193195 806167666 315933696 525560672 623306341 924166499 437726974 689603407 305476213 347644544 584133530 627955846 616125976 837691855 958909815 843536632 730284949 567773146 965635970 987485092 517907974 467335786 236591012 842062530 512520964 218925630 977021721 618383110 799747511 813031560 233428917 566110157 613394411 240446642 797190056 627579420 714322688 705484275 894010001 975663199 532523142 791763148 746947523 856300590 882074151 989551682 499970781 405512619 169864890 223574349 899728765 669056993 862074653 710329064 246794563 500302710 930203423 318643544 97866662 910205059 478682657 602924234 738554885 838737117 831588542 145501873 404622795 341018374 529713749 767836543 506672675 340130401 720987146 470467353 999703117 700368185 977814189 371566955 210361752 615384613 695040196 717262484 475300590 684877054 543610042 432109865 672658013 964566875 510781872 869754984 921330175 722756882 879827168 352897590 982490642 773884943 759004935 789227070 894016417 595207349 873100899 873317882 725504709 344468978 901249287 959488518 909618531 232950545 884540139 470932431 666886234 787879133 706896770 662273469 337600266 905783881 910156641 443439667 227157511 959927551 612096523 501072175 852338266 804062376 456379168 860347255 443279758 921101829 529140215 877984612 894073632 763560621 844844633 899754834 521618218 647537558 307368108 984724260 880857005 53720467 228369845 479491383 922157559 610246493 863562842 910219035 973215852 960775051 642426869 953488586 884699171 807299177 606007527 548965681 835933315 989872355 851456850 689444167 319888716 100441427 941067635 634840129 696957115 503002516 918057104 712266808 842816826 647484519 365647939 355476683 353778807 642697322 150156131 287066498 537976925 515003056 373784815 721051406 749427419 933198733 834333604 929898362 771114556 863469520 164610378 626442593 996771917 466403803 728816284 986702413 821049954 969634553 593786131 922050240 200251642 992376355 899324647 204240654 617626871 629417485 562495555 584914337 910951834 388996054 410851688 854328903 914689253 365607591 745767228 860314927 458951081 253928067 198113961 732143635 326442597 909663964 934879974 214785923 902365490 894395221 536746613 440173248 968490620 479210649 968387813 214988372 177561517 694018076 422736992 982460646 334344160 762220265 839122809 878831989 966518218 419261326 953169920 271639802 316814924 695048582 388182142 606457858 847182999 965580232 972661317 732665585 984192203 911716620 251955549 437045177 609962328 788393599 961526705 630845791 857029628 813426568 892685854 888598552 467465508 815812001 927049588 916085423 407879283 806566715 728525939 268668620 766436051 783030801 354267915 965770981 660111099 879986270 980734709 617577653 897281709 699254819 598026539 687346459 701893912 956652223 549984581 929256600 336447488 935113530 771930046 948281289 998207721 480942094 984777209 166686909 753668030 889752602 773616305 627870999 260155672 809424530 696221098 731228453 213876816 184797247 987802721 978819472 627931585 647474077 411684380 784640386 828226153 505565045 958781036 959520801 595677503 401179666 871395293 155332353 974982894 824884090 340360562 283693775 652937839 162397635 619461281 785413274 405691126 827083931 543388496 877222652 267719111 402675668 671579562 803702888 560412474 993642429 372443198 434334198 590897375 908088656 529344851 766920724 695441752 615056826 964537587 687110599 798106793 878529096 651710378 812569137 953168539 688409437 404092222 921784432 662465605 902224764 913836002 299415103 867376258 317298029 888428018 839253659 403618223 916457969 979236750 855237631 511696645 896226042 928465543 703297711 307551307 739346174 906546151 904206430 806076335 204098118 944395270 845097577 665599806 428924465 926570769 658901136 942845610 912835085 780500448 738690734 706501330 817296790 457280686 715467758 911176949 937327789 995258668 403513220 883623502 335638565 653639039 708295901 985263124 485107801 456068476 948475351 274647307 501810436 532590632 556151502 627044755 919776640 505344312 664467226 286432099 907431583 536041270 884163480 138904458 834596795 874002108 182948727 971409598 918068751 565615068 290296008 996653974 937941792 983688186 841463523 306389457 598993364 535350934 613468644 921992218 983955506 799620871 320646817 937319120 932597101 754914760 957670760 635732837 863800169 813743589 922905624 513641869 962443809 451630243 726330694 433403388 488508238 335645196 871857542 614981354 482629422 927987508 939013310 646223407 452082151 724505506 792276714 819105098 692447398 685617225 526037810 182634903 955069102 132756730 919383175 257424037 891362799 988677928 678454063 863242377 678191390 870174816 985365385 964339925 411712777 432026256 495825615 538728602 917663912 970243271 597916904 995604471 644440499 782420383 935160010 632278450 780109350 454938156 427130923 141211566 599737438 959311498 698287462 824212844 844654831 906417062 660852493 958219941 466970623 879558957 527316488 934203146 771517505 887866983 779789254 401452527 895447862 991514338 448968276 648265624 866735620 327132170 862918210 694516138 380092552 753980157 696755397 704034358 204326471 512741021 859870448 800606615 700285915 869268373 777745565 797461566 571479228 901519573 801416048 890083568 625427180 501874585 510715704 122246222 582728214 852398624 536927567 742201761 260283076 911561355 779783097 467505236 711434665 539792938 537063129 963408470 703072372 952056595 868920382 989062062 292906295 511057836 73116143 852603319 357021114 870409307 606375464 565231850 937631786 837607112 432743571 466060329 941717705 333225121 905515421 909944749 834398345 212079072 550709987 922377712 557619350 813304230 730863535 631920456 854737880 885700077 397047795 766212817 525544894 885677432 808440698 843490508 781590278 960852262 837000379 952988439 819466535 451336793 911004919 934718571 839506658 347861048 451677842 605127944 417347697 578103979 980354675 376398436 259277355 434662226 74164299 898362511 933010342 765710859 257217657 755568980 438746696 144328983 660914153 423844005 943171548 541721808 650940634 754238568 84598716 567208214 844833881 932285790 782818330 795185812 274290640 825074104 751532059 432397263 777187968 902182298 284062163 505767808 887989899 755143539 832586838 760274605 495143625 970648316 421565667 932228986 266432224 383800832 924313995 388570617 340670290 864556553 837987317 908956879 923245391 919715734 662969473 864529959 266909212 458968555 566763029 442728317 344190056 284357072 397829739 411501973 962056383 657064520 795963604 827957140 944930932 707805027 893692390 962581931 663484420 490886725 691500352 672849415 821625088 952118749 455353356 542363294 131377514 406282825 973043716 274673831 529822907 832240530 922044200 873213789 306525457 642771484 844057864 752790486 950049913 343700311 384525726 771926124 760875432 858535789 695086658 651561260 307431116 369612897 494388345 98356281 695649094 804873332 430358859 873079505 959211288 448587179 774604719 901404338 556883421 569112915 733874622 128428469 833341265 558612391 971286957 603406199 407868824 633987835 577714859 613995568 943190897 646439282 811178392 63839292 986709673 601425735 579048548 588860676 925254469 752499573 983036921 799593765 576554311 586158041 913936386 879279420 405764783 855868552 982665504 906529504 998615062 757616974 546203857 645010646 507883175 643502152 458433724 677248363 406534458 623039252 699333483 454331177 684412709 820428889 191120645 528946470 341066955 285316035 571578261 380859270 865088997 534350432 764632156 819346489 813541669 894113073 582768976 736171324 317224097 227708803 665437305 927722390 818579798 243196906 645396254 355715014 78554812 191280237 619590475 682043680 771329084 449255041 564520846 419472724 854686532 796959643 547370336 949665812 620053939 682409973 533884356 365038763 288491515 612332846 804816613 484060553 907984384 429429706 509307085 624748031 879295549 994716405 743684986 161064625 514715039 444520985 832564269 991128781 31457486 775335442 473119194 461385941 825007137 752681779 835624327 830046912 735597795 433583281 680482863 594877787 453008239 868191502 864272861 871836063 705031995 839862710 531506119 430064960 530170846 987847170 746516287 819047039 829864832 824853481 334844494 935905951 808345819 537362235 860771001 969380757 528474251 935853851 563767910 893760462 603114702 932345722 76235218 405156219 427931558 846885176 711234850 894352162 885783902 723562750 773138847 602342075 907004563 751880409 839458932 254633380 817713722 757696739 915715905 743947202 354288125 797910141 828863165 916229275 985048788 957660671 453680701 640299429 400864250 460237109 616612872 703590804 429395851 268272421 845580880 615341369 314729235 578297205 540529980 655585516 972795715 910916869 840408621 795328630 935462702 338453939 377229384 955363927 878768072 576021100 556670138 966587391 604981932 507638705 819443704 881362834 883044312 639032982 133011723 374042748 369518703 515271415 388351499 523872116 608514223 978080014 884526231 355965655 737223591 610588089 591005936 493458575 731668515 102448305 773058462 650273682 796454674 845985472 347456888 791654779 880175495 605245046 378947795 537781297 473451111 862137751 292206151 642690243 549508438 897370231 356680937 808213790 824473157 806592927 832704819 381864438 545877926 620609172 332863609 781810922 927938279 832407036 612503187 835793074 271339341 373147290 874650352 351132983 402773697 726236759 719264820 612611692 584559286 976658205 522831197 675373603 246531531 639511968 712888768 532451276 673115356 791491565 781116807 379985585 818365329 433973730 978637478 831073649 869504112 762361666 832657619 672189789 262414063 782632775 487998741 468509039 988771450 994540460 535947162 830198857 341124284 632563827 723199433 626017068 865507505 220877435 618172381 325392366 616302174 952527377 522079634 461513720 174771311 861223375 310134817 693636025 613202539 999072915 622488280 455156295 908913177 765774306 350985016 236879054 713485752 434125701 619717479 803057448 718147060 727527020 703005358 976859714 685757633 884990940 506337636 888639586 276323015 702680401 368380072 979354672 662389427 865032908 215766636 708779817 574924260 532585656 705998397 807952821 808322596 738592361 779254082 816510707 755163159 792324955 609282461 801661060 564273686 796030984 670682634 937499068 827388740 773971189 263701825 598609670 759857524 303420326 737795411 906751660 147853299 602954506 565184280 96490505 119405834 896960125 285414765 876191972 983581770 847024411 122275980 919220750 990594900 858366205 928036117 843319278 869631198 925668628 875452566 415628444 595789885 966161058 574780580 182876406 700155018 893100757 916070740 821561399 836635386 557676105 612635383 606291189 489933403 771831982 739111715 822956195 309433611 832054992 656645831 915392321 397257199 876051656 565749620 792516309 759498123 520715690 429012052 932762694 921349475 503927252 740973871 266718900 711606273 647570079 726173869 973849895 734870771 624411180 633814478 817150337 511506779 471239628 374137360 241165293 992843804 838262701 977890378 421402236 935319599 386435772 853641205 967750076 958330042 219696188 753882494 459552634 711562001 592036107 711180129 470029564 253321906 253749937 779095086 748981880 985297873 971940274 821193671 997734036 957894332 353545303 758576322 533837986 769584199 553109118 670882989 915527963 773991154 634027363 401632040 962178360 515059346 767493095 361468739 500212930 689070750 515907116 784534128 510137495 654559905 886763687 740146177 713914436 710289878 527681841 827776897 723793988 707967361 245779411 666022836 732668967 494298602 181146069 595657602 671256291 817100713 782959614 943312711 486224803 919452172 986713000 875551214 832834356 939988609 930340624 364952105 990568768 728467549 901390187 347923727 932135949 763748189 133706374 810529571 994304623 116137194 88895159 266355932 896103828 240165789 514643709 556627987 654114500 801587279 653562266 608691177 954919478 778587163 922082193 651601454 526337343 234043343 585260164 847329930 245220069 625020110 705630075 857483011 793738370 466658433 466054935 589495969 822914081 396455327 901053265 403599960 536999011 301906760 991975256 871662669 594197401 505249213 823498425 219438292 749626214 915449012 282536297 723446712 321756668 468830774 162224338 423243567 748032938 883580678 721273507 605924979 615319394 481893405 821808479 949575477 360923105 648830435 301208600 941634460 893796549 487492638 304492600 479815049 723724869 780857021 812338966 910178714 792605817 873614143 312580584 490827130 982064172 671063729 550741867 737939010 608460390 929525881 804551154 536009600 213931964 278912124 159593703 259739123 672984097 850309754 808549707 987514895 737883720 768506844 928746908 416589853 728908749 361256641 576173732 580223993 669390061 421006424 485703743 759833521 721181388 963972216 753288829 593705327 861952017 722072765 650874908 876893356 842605858 917225636 573919281 682100327 838709828 990290323 923222609 165461115 637428018 870742038 738954444 512410006 796981205 837500558 889377390 917213527 435559385 831237508 202092681 906627647 517273992 884198392 745522759 542094022 735993138 729665591 831206051 411860848 676066759 199595078 832831046 804421571 745846056 383644312 772012495 690554934 23357468 445769036 644707120 990349089 204035040 809719283 764139531 615721396 837524741 200343188 929521920 897044615 387268930 481951087 845623372 313997741 948818466 822850135 898778292 743575537 241138387 862497384 955480380 847324762 916776213 925523621 542752243 574313006 775042901 579468103 51870432 285482433 655865411 303580536 901260815 523075368 626904768 853668495 878539938 967614087 876485920 985904936 467148810 912872464 456210359 187353387 993764833 792133093 326057244 495265949 729459484 945261836 450794065 701437263 91521563 684576401 132224350 417412425 411663597 954731726 827231280 90761943 321858845 693109850 976923695 340660860 442749514 519851969 582180144 565897832 472630404 528632292 728363239 730279238 784467368 995134556 554828635 314550701 834026716 659522396 597231936 579256221 642069934 698596084 791764817 141071538 673145966 911174747 107130427 713951286 283553573 955945823 920181720 860559968 738622056 318199270 976298906 350426391 541891890 935184706 893890103 509204535 973179382 566276639 944715102 946435684 836387277 384081895 967625434 632434682 713049373 153926780 524809572 823860693 226077270 816514760 910083817 643727472 523905830 477507982 230261435 847993555 990471146 861036027 597780728 613805167 743272443 164916148 291159997 338161112 830719178 994731633 719825840 749818280 911462465 903950617 901328155 295592560 874123472 976221617 796287602 645067785 782118758 992481161 928465441 948617600 972408660 420664437 855341858 954219818 185990873 336057429 582839276 914422002 744336873 755499664 648120794 299294562 798351414 824956819 796403111 230157766 723866640 397331989 882779571 877030174 998964370 734838287 427587764 887792706 349930109 737492217 941743013 613735677 816051088 808674286 724879351 655675558 873738570 814228495 867355837 995417629 818923052 704237421 947767903 812856753 356547103 503312655 862244006 624270885 528586105 401323233 715553588 756879335 829323390 480455504 700627862 156383235 219587270 804721258 851644854 791474725 944492655 345089770 922056310 486314499 453207655 907898427 946904999 739372489 893050806 864158071 882347486 146779374 82837270 432270740 796633194 916388349 959307272 713861656 262965293 722960148 234985148 448631821 785880042 998387540 755622665 612180021 774103893 600158722 204262257 326984049 522229736 736168280 416203266 321149448 308513937 959252834 803341619 756091637 293305219 928636157 811797845 402399869 119277968 123536719 322686827 870720246 773194288 376797879 285979361 878048012 742365657 340660169 727649109 820538442 835484946 941014939 563000956 707984684 844261211 880896959 870432115 710359943 219472691 814503158 901543883 264177685 976818581 964111426 874989961 867430798 661191303 645364620 151124258 561402045 641837367 905110378 440808233 993217028 899387853 770086575 551177613 958581986 953831616 705982121 505141383 326022478 547735084 828406897 794098397 728126763 884053748 883829167 365490278 573504348 847484866 318301300 781656518 562406676 744768618 369481799 574764488 520415850 578021585 712346356 740273726 521603257 987086330 918145659 853636547 975493527 818241477 786527445 599112428 863173378 615734483 860744952 551067856 740811840 807201398 704259118 776571146 649923317 846924148 165521811 509892818 974892156 472600540 559867491 800066839 755421529 473311124 522363858 625507125 109136961 227453321 982786201 782617869 958324875 723012557 880862728 169587707 256167473 967808198 827819829 669923889 798307063 986300211 212902277 274900525 598429474 284344683 789403826 994220944 574535564 333932771 839368005 408309019 793972173 912162044 875302684 652466110 915014953 923571041 552002992 641508346 970930109 947888385 967379183 420005318 260745737 830902299 322198336 262604996 390213710 755802305 858294112 197729432 987599688 987610590 625038811 941186568 450974112 743995338 602961460 352855368 957461360 670915579 440018599 624106921 158853795 818111751 963490104 414245795 204831593 437861243 959200031 784150121 605925621 956167198 881933413 307221800 915598034 692870572 256727745 907819592 971552910 958776508 195724717 558934738 874288737 876018026 778306158 187641576 53157066 406671956 645643999 599010856 922114120 900958213 402001876 643486318 983535269 466019524 783318497 573374584 543610558 787843795 770511913 783497232 727077019 637517166 762045903 609608621 886444728 183144533 166741085 687708490 547434602 983407569 787162918 901009204 859600264 150099382 497847051 767234515 868170421 982107144 280048041 308769975 672871305 651908129 559174186 835561250 137749612 987964936 920810565 256774478 959540758 663256795 381693886 499430628 339773676 839274041 528533326 881591880 874388774 160073054 689101965 990763581 556126954 994303380 301808488 545958941 890271035 740298828 817754309 133286463 692889759 921122925 212866613 798006359 807256262 260264491 596874607 158867166 562999377 835302065 558434801 847336047 797898251 952676248 977516960 551494648 388447204 935025547 902166235 491422361 834349512 979438872 985901111 378229501 542658789 935068561 717500372 391373087 384003125 195890198 568862885 910480820 673422284 868404365 601757994 309959821 984820395 452751261 994395188 815841673 905013655 367749303 882718262 229811329 455867880 771346040 594629388 743963820 134612897 750232441 953026347 807245366 877664588 701331098 823224297 711450471 777793333 714858051 751921477 345560907 936852708 672418495 214252583 750202696 745709873 206521384 912029118 721242660 592964283 938052887 962726356 634786441 685673039 931825144 826176693 796511488 368847245 940358000 754682152 930477738 667698748 175324292 443174381 866022923 779087087 299372213 463045018 587204932 943983101 570706418 551284740 799032130 491679093 656883269 958797518 399447787 554008415 812233575 994813554 797309633 489836600 953482430 301156778 857115109 870291596 552188478 421343135 658088859 726466719 831272132 963083588 823812778 910177401 932218372 793797959 223230792 786867113 919773701 705821692 856870884 998766404 980700298 856026078 958668412 413182224 702013413 857901012 993811512 496408351 108761854 601477415 943688980 983117654 323072910 687175195 763657070 910559577 962195766 353239392 907113477 570385816 904651810 812910580 402767231 678111411 575398050 914625719 677391296 414281035 772379999 397429696 632116938 104636584 254633368 559737835 774509073 987541478 232612138 191403694 970873640 345789074 110477213 781614266 947857511 234873611 396543080 866739946 719579625 158797426 748960769 397927375 371767377 960918801 777049154 779634526 741259907 197362423 333050557 958734322 732351853 496446293 586484571 416612611 955172703 645676467 701043195 331057432 757464775 706012546 353799203 768177662 551784726 745724289 276448265 543527876 856337569 225412677 594512569 912332491 897360221 969399538 709802174 669570386 838059309 501666371 486840423 213039374 432040884 898674099 834498865 466645765 864440048 804599842 841744517 189590314 500954152 335618368 859166588 652621967 373866970 382314001 714211043 583050481 781803063 743263302 128939330 506085927 595692365 799139408 369953464 577467664 994431695 436296716 457244499 363435189 333085193 839303866 942423631 833374425 443350534 365741987 832247035 196202230 762675728 563896037 682390593 570193154 607990335 382996999 926321510 298400158 627795475 663101384 525512553 973259480 646976011 966127294 823110924 502805697 947611544 528187426 235021619 404800857 835727304 738241001 531082096 681162734 782936447 751504157 298148811 751168276 977739579 888705277 882149778 462238298 970932068 680712738 319694440 984282229 704831480 400476775 545194859 604504398 893888100 935697198 220775941 846978041 818967044 960449871 564732512 387817898 941569505 569017490 873143455 363838587 554276712 651392312 999847595 992880039 759514556 209346893 836527167 998838574 888264067 871409880 905490681 644791999 772538534 835805734 721509342 574477902 720278782 727322266 386168668 634150315 701217990 259251714 854536917 921453786 991072920 514150948 942630947 665489194 908911357 687651178 685797131 153412095 904678131 476105579 948721823 600374729 254211124 713403416 722727411 422739573 842684164 994111531 554940331 634498770 736380543 985541473 228420372 328607311 651989956 742179732 627737206 486778153 382898983 546669367 682032123 486039767 306719762 792516820 555227855 748229576 976756077 819289252 365216195 503365688 871897669 657444187 964203740 335938067 307388220 941387111 902017409 900294451 819212050 733769256 719829326 947272180 513255671 908413889 900788541 385751492 586237025 482880068 427602753 425727711 424862376 891932084 933784295 124851301 526500356 993354257 855089138 985323502 908021796 964514342 683525782 795648949 706044472 939266060 563565990 652840349 819418052 554888457 687887918 532916374 925692575 553349428 428050620 714543771 256785293 891191556 816807239 715599398 369846906 520864453 808381746 960618190 645952355 961692831 906530126 912805734 228417820 449482937 353385326 871687410 507301956 995520757 759012603 653361701 651669059 976855110 670923871 799089354 795808161 449248072 628440417 868582629 974796961 712898030 688667598 858640920 955507795 530730105 618276670 992286411 480130234 639796294 875304097 609186472 38569067 913343761 790447439 956806045 837985672 581199840 231287015 836913276 993252948 933189059 981444585 770154956 411543096 971012529 938258780 340451061 750020538 871532260 868663585 589340050 358921874 826162415 259495181 758942953 929026137 870626518 575000641 263600741 875474962 790548780 979684199 466743990 609803104 997776570 952963032 915016461 636467867 758606506 926691258 662480148 310290366 913499410 686468023 829474504 524805546 472286983 878615341 562849682 930162508 340408376 900480402 505629203 655608739 883087931 902180286 695891081 464661667 638654584 777455861 595221503 576279709 551222890 983207437 873063066 670824440 996319292 755695116 547425268 399113082 256572159 494759407 526068467 693628984 953836220 355787652 914977458 817971024 436969754 882660405 774751834 816246529 753330118 814111186 864402772 974723889 616928566 759357485 843588488 703464759 407516908 995296910 453619993 854453270 581276217 886828580 945147988 475471561 569343463 627883964 418754380 929466950 991271602 976051029 994273490 627424845 355221074 640357136 835589873 783631140 715729234 733487995 329879939 257418085 429948078 765341502 930344730 941194770 384900121 402193886 263391537 732485117 641091449 710368729 818279160 580955886 360944254 675569634 291506203 566768335 788388312 954114958 787435710 354157710 657946326 632453568 720885215 836540076 505641521 556805943 523561975 992566155 786686157 697394070 934196714 310813588 206488731 659787480 985680323 972699769 764676207 930344361 554732065 297887113 492650032 417792867 834157849 629833708 300409095 687653481 804292312 566361194 638416999 284874796 497149211 442814884 482797265 182482573 644643624 980096426 774382913 477980454 114828326 829951581 697645280 561984802 970635354 669752873 835964736 306359927 845732065 982471377 659660624 628244858 884569051 578442374 362896931 692461604 848832170 811546891 729048924 469407156 657016070 270770172 505705639 780400721 453424894 453645683 742337712 844756444 961028889 825859230 886775843 677381147 732241398 989932555 863269579 241185961 443957818 627301755 940596287 987815084 976892782 956638771 936616117 850912404 815393826 473709130 939659040 866239985 394986326 210251132 623232752 955947436 682107721 738028915 795497130 928133658 153490463 508803110 403755063 608167055 685066627 909455187 882166734 538616327 764162000 800600602 247294719 979907825 354540208 537079907 543306470 957437118 938838902 679638946 683636169 574523954 288804382 887383372 988353075 450801340 796281236 341783653 832713558 332236169 917306980 588872375 774845324 356539330 972641169 277401035 964698247 433207298 783082471 975910728 997928443 895558292 346894323 392558656 865555515 946573065 543995044 940788864 950739650 800467519 614651241 405112613 244281951 711740776 649375176 753803524 940460078 842899798 697848974 580704080 996974668 715997971 879424923 531372081 994813818 772587784 676170787 258828318 985767651 492330610 656406182 909190659 654510576 698621062 562192700 835448488 709359438 605121503 682874083 544912289 875680115 880935973 964360385 463383612 801303267 701237692 905767407 728503180 410508030 399277776 593399464 874162000 863256772 601342883 801838889 955619808 888818432 704052332 592137919 841776821 763934190 771622226 816280701 362470798 396340795 437255040 801797596 758443347 589084392 680323056 977884319 774724644 933056014 623484753 957250197 972887899 418203034 640007247 983383361 651721756 709225626 976807702 538431562 121647888 901325776 574724814 836667445 511639568 820657542 833958205 335126584 693125840 833786782 783152503 285202058 312644208 525316563 570170954 433878906 350767306 755739595 790142387 885471173 870857010 498351275 328828089 748913677 727767706 845035230 594412599 867519652 527934065 403634915 459624028 908390502 218221878 299709251 811427795 935186057 580377324 484475965 841303104 751980704 993093945 646196551 788951620 806270060 816253972 741777541 867112299 512296023 946051681 391471167 220239124 800430947 705534930 939238553 878200897 760529974 433816380 931289598 666840615 991695354 321413597 348153451 936601368 273869789 159821046 981274922 589337408 960074793 927040136 626198838 630557670 820991380 162965178 489958840 848334379 617259467 973556229 799098860 729690812 874802339 989619076 892739740 559293557 875141250 731827800 928876975 946131785 676445532 923479202 668904910 673536233 816042290 232971099 446594479 802725494 165266023 914108527 712135798 795006150 921643873 319840188 370662477 559682258 473665940 852915895 305087251 704045186 813818868 987769032 973496355 925107044 915400490 803283032 442352916 734625970 508994485 531198810 514408140 766352412 439483278 365055872 892685462 728042665 732154207 303948170 852154590 951820608 590827583 632969328 202696604 605364585 722408753 724540866 959021243 738194693 791964399 211682705 691006799 981154090 846042277 327991667 921971329 929048432 582013630 539308663 917704811 581468058 623957006 715987790 221302452 565025303 994747143 285755915 891380954 760501197 527957834 169906758 613924458 812351163 308894175 269481160 574904637 272923340 660775505 894587305 654929053 741668009 832745073 513416799 379441383 987593304 826147625 708569274 477735822 856459386 280735454 739539952 893017211 376657967 739277152 774174581 197022734 432584526 960204653 728803852 561793084 690678904 289150992 816306099 679373235 838940535 913111604 570751324 622660146 236122320 545510450 898378768 217523399 118354948 951020869 862551392 962298804 688892824 954967075 700073455 836438670 509191258 833916435 473603738 360695609 971599864 401473314 987407143 922592780 354384746 379460798 855310900 371659916 615155276 556254115 804457298 705062167 664776522 736931563 779760973 889313866 689322558 648930967 727632804 829945605 942071521 508419736 796098312 945706182 766670801 518907815 981723886 686676352 798154439 677519594 751744313 679732903 287556832 439495201 719245821 395861241 734743154 357219255 419272200 571351759 896113375 613942545 288567331 337834994 759374521 675772785 755138158 225959237 490436663 459613035 211676561 632000551 704480818 618354638 297442224 788570114 443356527 943166633 948310786 720340480 976667421 701331574 566723859 298534069 803498189 527893008 920690822 947788309 853931520 981773139 414703533 933793130 899115008 516594306 524694882 633973189 716961530 451773964 811893676 617160523 982675781 958511428 938912244 936901862 891801275 910916508 995706601 320659350 860225207 776443628 387376797 908473665 691038285 510229079 793338600 782470906 654025159 694545046 759837078 666638654 489379288 460316940 726462438 626598929 778255721 986418970 594433604 920728318 971497705 828300212 529648175 974766356 867129467 735140367 628813970 462042333 209158495 906479227 543360541 959708752 380211533 184916886 606168503 941656989 714645078 252613294 179740492 406545883 292652795 339633364 882246098 746569831 358275753 716321002 42970417 824876781 929251746 920672058 710349625 984481512 530708735 500739108 970804890 190060860 390554248 902003595 821176203 686092313 287648724 900424949 278424030 807835877 838324389 347505458 747474033 982560349 865053696 856593940 727639994 424806555 712296006 622063999 688932090 923436639 837064906 755678408 883338379 833971545 507715794 839544037 860540527 409352543 749884914 487572648 723058008 813991919 989696301 958872764 725965602 449905701 714629355 888695060 376314335 483201137 742031391 647678283 850555703 844878610 867087683 489101341 170280604 907685442 909592818 693532538 613073786 930146102 480812678 475336001 566441742 965093456 595041034 793659502 445348845 852941025 917771459 832870059 711391176 280962308 979665831 528219412 969865747 34204980 743374636 962430283 628236999 682846363 694750914 609775688 965951174 241427588 945772653 890249299 398478160 998193764 338922038 970699517 237155954 987688448 920678165 372306536 843214061 603399393 614087147 876672603 461787918 613189961 623203626 499543194 593306017 932703356 748662608 483039416 504335205 141032616 953917225 820651727 819280550 611519058 279705174 305799842 180273221 517906138 852760957 742779558 813570978 827672628 617469949 714798864 933813664 898299350 849089575 769246764 698064102 928461527 608776161 504595991 831721923 903769593 901556165 229242271 353130601 885830258 673036289 869993438 212426782 985575617 354954603 904287689 855558786 912528678 872380415 143049909 698799038 864735007 997442818 795435888 913497180 756484123 779920377 167624636 796837238 700458812 420445508 869094454 80168141 800911602 939303989 712171951 847527311 248537245 762449146 905259828 270037149 904197820 986673288 742130185 947192589 381718155 732898116 879345348 968288806 735165175 679427805 851899646 536488435 837954971 595814846 774312457 90210796 975336319 855685341 787531201 547360763 982076125 916943613 484456318 619058304 264598012 944762169 357051135 422954932 41754267 919253479 373571013 443299484 612901860 575237313 969031228 519685151 794894637 120258344 685669934 556307663 501997317 882359062 740681665 931884451 587585301 329031627 530601827 647514367 648499665 908278727 859298432 799780555 39304387 956319224 889012066 990650272 661453437 959843415 962546539 778561318 624628768 608762542 654813368 259060299 961641829 580467140 763585600 606979863 594375513 826311565 652001820 673643139 645458080 656640788 907326408 324528900 954576987 649187159 669837787 913182411 605517374 787890997 924156166 989171509 782841219 512938095 910060290 614661107 676245747 707801880 386356224 241497295 676059906 237674627 747885169 213537927 423529481 507135307 882734133 480030826 827060177 446467795 518034682 887655606 896658596 942446204 979483468 909116773 764818376 733961255 202306220 574881853 943160205 427369308 470128314 579005706 430988617 289515870 647507368 541336085 968059529 929013454 992097078 304678755 724811111 210201374 316064808 738084553 670733598 784772514 942258566 622660879 776973551 181569617 687109211 804948213 847005254 455913565 509784106 380866624 700533964 591934478 749665206 927935112 303270615 733986754 268554679 896071166 623442906 943871784 830980554 923110170 699720192 877596396 856487090 353819115 469213721 735418008 673998600 617350133 782753661 834246946 785400254 867875589 382251894 436967841 778060103 529301916 452222411 460064851 860001724 753611074 712130068 604796703 309955214 903001803 551141788 881900817 532547173 182531109 509208924 553846433 424229166 920434139 865560154 959558102 732964572 491927272 843912069 427241027 637609557 780390602 673829038 939383091 331524902 944188494 649036321 950355534 387010824 276321822 958386819 614012842 900420881 901579078 566573700 428079836 837052637 295526571 835239874 770083869 884882981 496687113 620457124 968198438 620656300 278654384 115430522 594394458 924768923 785194521 587592719 305359430 978197976 470882670 655622668 829471583 342771942 134429879 648341403 887523347 506138189 990639803 943631676 600309544 853205508 590499526 577862577 518024960 127603015 960853221 826019079 760047606 850393115 867869349 650502493 533936539 925608636 538760282 979540207 862204303 939815901 390423376 914720215 671458782 610052264 556428573 502121068 881724405 655028929 551497350 392609644 911078963 964357525 878084581 952586969 786541459 955748501 547134334 879412744 394212902 745380542 254740981 759060806 692517935 840085093 947699735 253822034 710562987 774925840 895477376 807947445 930991644 850812773 541915071 751850149 577413764 599102664 420750938 950160982 690122838 891759981 531612284 252804697 595950404 371117037 946086333 811172179 968346005 972452481 904161070 816640387 633909484 834804612 690326836 988480281 449521640 636154642 328140230 901173544 795528245 894390861 912447801 534828357 754495777 976655618 933552198 887095830 479950078 925923877 274702118 347381891 166153770 972597932 678865720 922528197 218650254 322589010 790748178 826555196 808162815 692885283 885093337 667649914 325882522 670594459 938423825 614911928 929750398 454770309 358592363 927221484 830943234 475411903 818738661 766680592 927520537 652878541 925587483 845388249 697168380 551491053 536157852 706776897 288110710 500029482 966604159 965071176 785016213 801863895 728711266 837761524 811035268 829343381 994049485 683411428 757947074 797079460 904887805 831470458 429263608 105941612 208861702 155307812 870268225 602082908 432867735 767147922 410031614 663683001 770322168 280070329 803557307 908228788 851132480 775624731 513718377 987824466 659620368 467572203 769753727 354576746 952966968 825479574 693764011 884825461 641534919 428329798 710496253 755176206 768999186 601848437 846638293 791856515 651737913 936674546 743306999 567397025 964836742 324712620 693781246 326959523 729245398 566785104 838118777 874436270 915867566 716560284 726699729 447298038 392809116 960232452 395675364 267477491 945742778 888057576 485930726 756548083 658480234 626512816 995557931 687586850 868140129 936195952 800935364 761108617 796467461 646584519 753626583 901205938 763195262 877172864 915544781 781855771 571933739 250326539 284581850 736374462 841729293 231851166 926600859 232135835 439464664 563793361 536055178 763249428 712948261 949587776 81456254 879541404 899140856 769879516 389871718 618502148 402875415 807105357 327647517 551275361 513067609 869784882 194055611 947046910 615415834 933390008 643078857 487819533 329523388 471840088 374427034 521214067 377803601 801940574 886882156 963345548 275428793 331616137 658041495 534425228 495351133 762520751 680914361 825416088 793128943 744049531 898202851 438523894 734186548 221007477 470470360 975976319 996612789 841899424 413897106 897128827 598485731 673630136 614701693 500714870 842684149 979175345 810738833 656683751 776355949 480227728 813632656 387698931 102888877 939644744 960433459 885982312 529139682 431030167 871892507 651868035 395366217 977594727 597790770 927226317 984921996 956961651 416339069 714526809 192678825 700298090 231399666 675863124 342734148 686863145 372283720 861258687 927004396 730065042 354315241 880800846 922614110 418582296 905057225 676329101 563861751 557270855 367679232 651635364 602950451 919896042 201782702 892852233 756226701 957995467 640267087 684588916 859542663 737915764 411573761 736232385 858660886 743121463 954980868 917112658 478909498 736490059 771364847 386563810 682001744 645921409 976152032 409532698 678328923 761039948 604573119 843174199 914028360 539326758 563803804 547777554 931531895 939283039 868258779 643752514 629347104 458712307 718610191 829550338 578982420 916755110 936547863 676370615 838275872 533083954 447952828 420375349 481873593 991651298 592592645 976246112 809092253 908693838 131808240 453110950 825087347 294887798 866444318 836360559 901457604 849039806 969656758 718699848 815140542 761549616 985392665 624830061 480934996 892269229 654131223 686992588 882254186 391862009 829945834 848477170 163842452 811967143 986222269 665052301 338211403 312009890 989073014 506813507 755767433 929104980 989389942 538628708 978832152 883055105 812026996 435553978 979333382 419382958 545308757 685180130 748420377 585828733 686067883 862626437 78203798 765823854 613837925 588313526 513522177 295807189 911434515 285556823 944564139 793529624 907201172 743682264 425070774 942966140 443469033 866499326 724071888 766657267 979833972 423822454 479095902 262871249 958147858 906785093 875762795 559953249 182474374 471175632 972373883 226615817 697169442 332324489 563918139 479686962 994975634 604305192 907134140 759805691 873053383 908114126 248903709 469456996 848536871 946051092 977192197 958044533 514266022 463436792 928496728 279085135 492448995 698885371 671790477 219755127 668824599 584546054 708301568 824041360 503125027 886101571 821995269 689561777 761253613 833950789 958576404 594198391 648555939 742677451 789776874 392705264 958412013 690475184 850656827 367323585 821196795 869365598 758908621 931609368 517791025 715443482 991411814 724450848 219451714 736095052 993317686 595215224 913255511 909196038 718841874 702254274 638108990 468479884 326597201 547562945 341090136 629327259 997621283 369713375 355595713 862772855 908887943 853223290 559245799 995141210 967371324 853977784 439262222 194576918 486081542 615103082 688612773 793269774 532416387 627148977 390064122 155393420 835947801 402398537 196662244 260199075 108243641 656957409 819891046 350552970 887390356 946492480 693641752 418206046 686021851 655178216 988539959 386503202 654217827 838799981 740178096 284549985 818105754 315734589 902895815 676138039 703385856 502415461 517877873 993088420 784246892 480995171 497850337 940348474 939026059 659064943 480692546 869753456 962403399 968343429 756155984 732577011 928092693 879078436 853391451 967205031 717777962 611385457 920429690 557595934 952475012 204911299 632894254 677958129 804829673 126521921 564008070 968859666 714559335 973340634 850860691 755968452 238870051 371221172 598082488 780321105 913437179 566742581 929336143 394974679 633832032 683421805 314681419 885509603 972899965 990453274 861266278 546957986 807975711 498387711 999481613 909078470 613435952 362715783 634777592 786174983 173732902 473057185 895429538 616471899 703495056 600499025 571620216 639463894 195376275 803678792 641511997 990886692 994958923 837371421 793772156 754370433 647419691 172174303 135836142 309221740 324415954 214787472 486555413 669955283 828354594 726136413 934830024 759868788 921884534 409500533 327863933 523918620 742586273 948481643 268036855 781561170 354977048 740267287 950414430 970932468 885422452 691695081 382637160 750204134 971661092 914828332 841610121 944869229 741957617 874438590 902690885 842833091 515275258 633754480 412992207 649436106 391479828 523808419 564572683 945019068 895821908 620384416 689623193 765189199 571169443 767435069 808085910 663517665 949675921 316652202 566856752 901531082 821253373 399959224 513977744 298829367 309229434 670498758 559955358 988142547 906863630 746531234 927031716 766854664 777780998 771485125 777471296 560527718 680123962 866318896 967193576 748680746 330194891 820335201 877197199 461979060 932332575 65589443 992988216 826940325 901883146 965137937 834157429 724831872 562650296 680112435 745438059 955416511 583504667 401290349 767959815 323327282 826388610 923172356 744428255 674551931 939153713 566567568 533358645 795143573 373757625 186167606 922512800 598707544 203593219 834317742 395398930 822840242 712852653 635053873 468557197 303158159 948792355 723739439 689721111 957887172 413879924 651786128 983825044 91256405 673212731 875344248 239723430 415666948 659509294 437308625 384618881 938116340 344433250 338366660 458687837 828851552 828671984 970775515 574044010 378159000 356095143 912083180 638340016 462743929 556263496 913409442 864760215 609374200 520700989 767061436 407952043 868872060 856290790 337204726 711589544 449783340 538000939 228659155 178918747 829541734 490782849 608416043 847577378 576065522 744301116 573789732 958690619 560322971 893524797 761624517 329929336 864515111 900572560 362352745 743468514 966765719 955932390 676662017 913502690 591994505 953515254 570658630 915701192 644886069 898983533 171068372 594685405 396291348 758300118 900967073 991219968 868091650 797433775 334865245 248607688 823935226 747534363 557641864 255916924 747106199 797557267 551716162 691294011 643337617 964144396 936294990 328810781 450365304 659801602 653978064 874206760 560984105 971318453 592221965 887951161 990648645 70364780 350367687 705371512 906259174 568735877 989673052 273554621 973940032 933211649 814796397 922339822 841151117 895173034 231286497 811978999 918760942 968317693 672976177 726650729 650465366 746682046 536640109 603378062 925604145 909416465 978530475 117916063 655415426 489025968 994632836 521929706 648865566 554299712 446112282 891188644 268359141 960276907 386547775 744739260 309340310 992823256 801923475 525715919 634970462 992112571 612319205 576194733 983347236 901058756 446989786 786234821 452046407 777374458 839208632 361279682 498926657 977776631 874669647 521259594 948905136 846268601 965138002 752092467 636428469 857395413 967736672 364791239 915156115 595947247 957933899 635285455 660590995 560391908 547509743 484677851 900512573 909017482 580039136 789644546 472256707 640412835 897415671 240657020 696540191 947258884 716473483 973912503 317260888 900885308 968770866 726037691 979702969 674205958 660512060 176320555 680686353 907860373 563299577 845889590 842565256 875309877 716146259 184194206 437851480 622329493 893107700 678195678 634993542 819181184 804116292 968847361 816427827 796316215 822773051 850044243 924209669 911642536 853455010 755580179 962380808 772554283 856974775 686644149 960739754 906256434 187268649 746475850 634409423 613364300 974480141 400527063 789825421 720782454 857623112 434534358 803057023 645595551 875788479 317282862 559871495 988847709 883052157 794227607 728529968 922276791 833125215 512847680 652890146 102341102 664291951 988874505 948336802 502056811 819142511 376109585 592113782 906665525 595584946 507840988 775674551 884393475 767363643 846914957 414983438 554744642 658974168 957136627 93995421 890677692 889182288 147501356 576493836 809047805 919433133 934489883 586971997 437185216 86697503 970924896 724611153 700687361 471567520 955895110 922588242 498825603 985043285 418464329 358980318 825685320 242346387 518132639 586484957 434529845 949343059 450855906 619401648 797514696 746242274 951277833 647133653 810909779 329245621 589494617 936092714 984776107 975480591 864153655 968075116 925126294 666177673 752636483 801692792 498746644 450097762 840695564 889104887 981637025 685049563 436719883 623784588 138691031 471600666 625717597 883166531 909306810 729957823 626649153 380247513 362225479 992099723 616909504 900559814 994926363 637363807 926695200 507154787 692165538 792963393 946701828 874310691 407446351 903289982 770076746 917417080 419466645 342669270 680038846 824338430 968377145 480060778 921695170 677936718 778191739 99110307 605734957 302911190 743474587 766791221 887309018 368120517 570297265 777326928 840183605 516161969 655595643 731592158 833075463 897768955 714081817 509370461 695087930 949082103 843185001 864430461 134736468 453192839 117646159 982913523 724059200 563927799 857098721 562486285 527964215 760242720 516186414 641841589 697514438 807520366 472042343 245371110 165590826 241874785 387111224 769884190 699969332 387386365 719921048 481515637 778700101 593514284 374983008 601091813 829427359 612843029 132211538 415681223 625566492 634229317 619518864 501681884 930585766 642817430 782922506 606750165 602064012 968082250 436137952 443287210 856321809 962093924 449213274 778710936 920374902 314029992 284881288 336354867 772260348 990049454 882854916 829005010 755535879 467510154 732797106 721659232 569462091 196529583 861049678 844498055 656905020 664155909 782762754 729953699 953030094 402167342 430202726 776754281 908211368 791410823 655141950 441931018 990836176 260636469 349384515 575232471 694789658 601999924 348335073 462739087 952806236 334103885 409956119 814361192 572024835 866609466 800484863 804357358 987319975 830063311 851388957 944939116 936110708 705510460 878589971 581566630 464897266 898948594 194531226 875860308 759922688 541721677 637978879 248824128 565036505 844130917 954006054 742907066 936650913 313642894 971035133 141572540 344418073 639810572 952696691 939194990 519091838 573082319 648835711 991209298 887963423 887490921 658298909 921202539 415262096 861571430 376275696 605030465 608324630 971390307 864190757 428588357 352424764 575803718 745468371 546658999 789519477 666640577 874309973 640087702 946015188 620929325 344336896 422646453 473143297 116830982 704533912 512077107 263726702 591705609 970682805 849363080 476406901 748156551 901100409 580501884 264913054 908023306 468979591 905603794 897447548 469454829 834412152 444222719 427924298 507787199 557548454 361306391 320876999 902657222 991753797 745814091 560560199 317021044 750732467 282633687 783081851 697733375 820556103 445732236 385606023 637107433 412813985 501605187 893537160 819564842 559480026 692576268 597113579 507845880 941015668 708065471 992050134 572613007 587206199 768145532 340114310 439451869 106859756 360584104 862794430 537051588 582686989 309103150 812212847 659618389 908308578 929247981 772365659 899375905 513483627 547455308 978584723 738306063 174630370 693533599 967154667 715349483 863805145 930993742 728614088 681510360 821111361 950180698 571492679 958980718 294514803 614699750 199093380 581359909 799455421 510501363 481452041 843269466 934820482 419448697 969515707 447869557 453092053 953780085 781920844 787816414 874289417 970610557 822921430 866214931 343711079 678771100 744951292 631611665 346147537 824951889 635203371 850541542 929842723 976855461 756838756 750933797 992992903 465943112 856081083 553043435 533937585 493535034 430113154 719770472 694940212 529897459 925447699 464489690 932684012 918178019 761830551 973064009 263326508 799508858 800004276 953741341 753132343 959935592 272328788 923079018 561114251 659926106 463657500 557754907 655933181 579784380 690349205 570548211 426356357 399914735 551268349 455475126 914081367 690480002 362764000 778199175 508556210 608211429 977206481 799508198 720904648 589046598 312317084 209157613 839459557 489653469 620762796 729830490 916638437 560336348 656326223 304839375 244863322 560269313 964232401 726978556 370812296 930661011 970960278 859165166 903738419 659262471 579792736 570891556 319931576 201486225 889238091 360114069 270857880 871183217 488866869 152684233 83184317 451048697 979333718 590223444 677337339 497500970 717379923 969471965 283616021 457970366 716500183 464828093 366280027 567640351 406417718 727307201 859013438 233182430 499010087 848791485 972471314 418998170 516231824 995930029 291323904 784535096 852324236 939354474 610992599 811589235 544108188 636190047 682019868 770113521 889996087 792516362 160475178 849530997 907328618 57843152 825998253 888550724 690674762 909464746 599759377 426142620 668391847 511033686 740925118 799376160 716283296 350538611 634787579 201754216 688553773 513500900 655442329 91095787 895534347 542112064 633842180 481344351 772030992 816785341 759142616 769027769 434503045 429235827 786656854