12355
689484429 245498424 928868135 318237576 102913631 775138952 216409676 876189833 115869800 816291556 105278346 11200951 31041942 836974660 295596573 84432433 678831907 887308938 414228706 361234840 806173477 457335899 187403414 323066167 181156169 359833429 211003653 89793947 971784948 502464845 105122653 661269377 747963268 33990787 979506952 850876898 661646090 48432979 579583083 630032242 864724535 537377780 641233192 895766476 226868791 936829764 832715261 905700697 676655054 99460318 266935537 482828530 409312569 306855302 658411048 590468737 666688730 869414700 532779035 638473677 224395896 637901687 152259405 972359163 671892473 984282709 675752413 186054914 32715687 107851847 816087155 897440221 645229626 457320346 645723049 872098416 246666462 330954661 777799113 923321515 282931330 897251001 258666396 692243898 204106302 917077444 135228986 870795031 639008495 668008020 361785059 863404391 305909706 366560816 688279905 830318530 350843524 216548669 16373444 236075562 324400515 832460598 133515783 969630140 142297296 631755183 841728556 388963757 815226195 472044020 164801623 98157524 221811372 423468018 790401422 425917673 340545461 925630407 149229055 979553956 446154779 363530465 695474698 752064484 730091280 383754602 434899366 80934803 600303271 451272809 169526717 924703785 136249758 155558851 746850277 131063405 787314033 441095184 520027161 455056579 913139203 684828783 553214102 134950574 108296801 196131875 413384598 301358613 974278634 415130004 133428920 420433412 778660468 828903617 25014247 508751748 65174571 459913612 442202902 517994193 763702772 611729618 295214329 899952530 767288468 42064605 31015934 407118852 483159788 403559447 862175430 248815342 940904581 267905884 236282267 901717733 316554110 502183216 55592698 290832743 917313219 189021617 563782506 695973687 870441586 588796753 57241786 935616156 901226716 351961039 306126700 664929488 963690657 601341028 417398369 583495476 643405633 300930654 843130680 979081772 557006452 557822461 80413466 497911033 825728344 316695732 252145117 142282454 818878948 307737814 285631548 588708518 496759431 849414054 137198556 219717368 290727158 194440341 7849875 44470225 546401380 313976574 709399712 362608388 915317601 979314432 798620215 411239585 132761438 641750894 390321357 689767889 52089707 470734822 40195273 877818050 639946905 292340390 872616855 311342204 600078203 10764755 900050722 96837633 712695160 37249277 169071352 3422317 84205970 176921226 47892541 630607349 490897799 609808605 845732088 406215400 441639388 644352302 817454984 574400825 138619548 60292692 264168714 190709254 383543865 304363986 921043655 23490770 596704375 646176862 334832973 49298930 656941616 87400046 146136562 222153127 124649323 167724266 78091795 208855292 344645491 125984335 691978992 835543290 588309291 537711079 94275041 29948679 34579732 911730024 456865855 25715631 824539068 721034568 216424884 208082932 877914906 137468539 84090053 327135632 636161752 418923026 376434561 145619719 506323071 375087475 367772845 483488745 542811740 445864639 692344036 887457230 424365325 236839379 723000519 12674616 774550457 817275559 895139646 661646541 581521935 204521852 687362171 258577354 925556420 903787055 466660285 655987677 893771945 550750338 983123308 382450048 822189715 359557869 528069766 181029137 734645343 895842610 664517882 129973434 341707248 209378269 17430663 766072572 446217648 592947534 631263539 73284456 262739444 378919536 734930996 844261378 583441388 422293167 102838731 361514159 178596573 422015368 17501835 924884869 825282057 853141494 307334916 647471771 65215714 835404681 828500907 799861056 583763642 345535140 929834489 925470889 554913409 799781504 544059812 1131056 392729037 27839703 74415511 655468480 259275590 809346507 352246210 842716977 84156025 307601292 56747487 115268949 582133011 926765673 40153817 407415067 779907167 200005084 907403189 845122880 35409764 588420448 497500288 471689757 933955587 279851128 249676997 488868995 79632631 793736808 342516402 324878019 674092862 416931913 832862851 933368452 78794771 37625412 628601780 15467147 345226703 685349267 130736095 927359714 464631291 170889911 187291132 97054809 370894994 94694321 942177689 258821109 535631120 292194328 730510865 469586706 424561807 980187861 810972053 356710790 626441020 153488454 681588808 153050234 422936718 366968010 86418685 501731488 404593421 715020464 517198634 749820124 252886082 647934728 529696189 717517373 671340990 569503672 814572181 42235983 516714344 609266221 153573443 52345463 753976900 736600659 374448521 178538707 569304871 185420573 535249496 48262243 191425378 69354655 201312476 614362096 436322665 287731160 116093583 840916085 855267975 485808569 443252560 108154057 986259648 825465100 678187781 657600638 394968772 345276313 552352972 911683115 807058886 558442767 816544930 561035785 295043425 190993450 592090843 864348296 228930374 127340338 912610538 420355751 49211345 113923013 34717846 338050361 254170524 3327781 31482797 109438498 341652701 474735357 70108906 327912348 152716808 600813038 838029337 547685579 798605703 242898661 311885046 605664588 801341427 128429975 19216724 96384851 171939776 611307567 813249498 400870149 591164256 578376387 821225899 492891952 544815751 708460097 830942312 651502626 711787877 862425109 613457476 53440577 189676817 536082733 233869276 342393624 136895771 71898613 890079203 788017825 167313625 54480600 246198764 968655051 35426926 265415487 917556253 59883053 729239405 583322103 460753201 172920013 14214841 134495451 665811964 559030592 842955547 496754276 63049569 407259775 211695736 676507044 313216703 401372552 212589777 399602331 743766175 202001899 324017295 486361729 990019723 491330919 540842328 88734838 459985969 428785605 354150324 230058573 488668657 83389729 813380675 949421857 108826093 827595516 936433660 774638056 239142459 631905558 123908683 302192027 39165333 335604418 978699071 204898387 736976969 43805199 604500717 480743144 245807097 928518011 967104872 88343171 272365281 360463552 177078008 732351249 789249156 383744683 962409822 130434165 319650763 628306848 79856021 428476855 455902363 868806032 203114911 695044821 500711590 327023593 997236848 392393274 662628011 828452270 449808012 252121331 872257468 54308729 732864474 118064564 835343091 552485698 58924086 107708372 765465601 88518445 692575972 407231108 472263127 507502145 537665272 791913890 135808993 470037645 220390744 444227707 338843676 276022006 991788880 692071617 603045599 841542079 84464890 118189961 669994348 386789254 370311291 394768167 293614334 955692117 365349082 128957424 360694166 424273167 89182147 126159766 512791611 634274471 533390873 985054737 994292967 71056145 629484978 982618311 393610141 849875722 279362370 732453816 125897727 271151249 277041785 581459677 112693327 214023026 552165989 635204026 600812279 922477280 29972192 894426612 730685748 247837625 875900388 91379913 672110791 817598886 70056030 37418753 304389708 603446902 874989841 298682675 527019398 504474819 133817337 920629538 206866892 413179706 505599706 185280970 684330954 782641490 619256999 649540632 996664515 171422987 137261009 449993146 946416618 19749552 344419757 677102365 267587176 72836496 620998629 792214318 890435382 691054658 829633070 194825089 147017912 557139263 346024115 674037309 61614081 479841452 447183199 120997324 893021157 805299256 158794645 429868463 440457097 778051643 79409094 289637963 949474630 69186455 739631108 748407599 88936006 84050865 278026316 209039534 9403712 899024944 1253851 899839093 590079602 683403273 94664182 737097513 93058887 293204648 263651173 7189319 773046099 563350723 128186642 666067256 368649978 286981286 95935718 809107074 65032929 27861163 98745037 867023910 949563969 690892496 467947860 891016327 627459712 745974175 100055860 636863424 644999119 953826062 536702516 87595072 489745686 483883049 677208936 582804572 777087697 940860108 589993890 402650147 356727183 570696883 68717402 725377160 857678169 17169471 387000586 775227449 897546986 338261974 494767710 699627306 29154469 962715569 590643632 509130533 561206096 543215843 145993956 58721566 349558257 535212823 146316637 691820294 19095872 823525572 127141218 648699920 616902031 717135107 51350066 973629213 140348342 972583820 551522725 998026510 842269642 791039662 625770310 592332979 129301635 973054371 144476637 10972455 788286291 735120268 372619339 349492386 130852463 518613294 408213951 332927071 53826117 407046939 24747364 925438340 83088862 151888581 426654611 699990893 721540040 330521028 526136457 861888381 155621199 930175533 712431242 850407193 721215194 190717903 295256523 703033180 163772273 439733159 566521987 952058563 27369779 939141325 154067301 158222241 310270971 414797603 491149311 216613439 821844542 368413026 994568130 904933403 520301607 273739092 457440647 94357998 604260119 983577104 956246378 612397670 766268988 668677619 462804862 340000534 859395521 758061384 43033713 875684145 50310895 462072051 680259059 77680673 253729728 834326359 235902913 416517050 101640314 579568575 633130488 923484855 947981600 480214969 828418257 320799558 753954060 138375256 415157555 210730530 121952359 371403932 823128199 740737698 892597902 138449412 80738231 604509774 896510796 976288296 480193918 946821690 290876698 12969329 24502362 544606425 847295687 112921626 961123474 948936000 692490200 446770313 724937206 492988151 926985281 405871815 813787709 533455692 544247070 228945263 744186222 518715780 452865547 567314420 259453477 345463448 705763832 192708060 949973222 454790979 168996355 282683491 254129020 459873052 295652819 131147733 856995829 995464858 96585710 670635654 796917209 789075909 117405967 521854415 134580411 896907599 927726229 948368119 282879643 324489650 29829734 27065864 843205429 482695280 446896635 102658905 828158727 5176818 147883316 630648300 459967796 316879670 765848143 566613167 629269074 61500961 697760899 486264902 909482170 794346608 9416907 706399379 435938868 126822873 80770145 570519279 876246824 861012725 371403749 11642818 185502374 401233482 38708681 28707802 883928761 485605315 983883058 564603840 490782133 131766374 47768491 803266280 301162395 813616633 369879447 930431468 727633946 920156697 269212721 637116115 567019657 278629628 196031845 2958524 257968852 129318341 425994154 986732027 990331065 797397903 998374844 28349790 51147736 37083524 57057591 935076497 375205191 893457001 499680336 718503675 877739726 547448826 521769954 31418472 213581811 744165752 814366292 941215756 664322449 83579012 430848222 83858457 214724991 626880067 86816980 325210195 756198407 365327486 311942221 599045824 15241740 162833417 627395613 66389475 52433292 536969556 1465971 427638482 282942908 353662658 146142156 13198985 753627836 520428462 44617456 967209646 117110565 858983747 908425401 781433013 795079111 191789974 865291469 862320453 818670040 804624801 187530647 427384799 22468638 351989220 26430622 37710377 514822636 506342586 956616203 567255927 43312141 810598526 994894409 326255048 16777535 993552916 339454032 770405370 366497729 236587840 737615015 483608294 95571586 498556767 117557658 743167048 690346741 835365479 458003853 361533132 492506631 645534499 641434282 514975268 997523718 520381255 405201996 364862705 26723841 214334550 932118632 70035981 24933075 779529392 248807381 41710610 625598659 440777764 812115979 992096388 677365603 402247346 328221033 625453541 753320464 298295042 221136940 296183556 133660520 679140792 657716688 626167150 177191643 151667321 993658769 27231712 672048576 251377116 392094417 698772416 465711666 324213048 621324748 490644740 103742439 722648480 384871701 581857449 163426244 49504032 426470188 840791846 451751377 754691220 318761738 57588192 52986262 539898678 353771748 39163133 219039469 11488435 517846635 396231111 15672107 511505403 423462823 687720682 762882519 815557239 239009449 81110536 992286638 860334197 571755275 948545428 435499028 956626976 530402876 598925271 6131007 956873064 292233469 310398735 564080635 610995206 367986926 469583248 3410235 721758673 361262733 222449704 585763459 879109367 471197166 601435566 243131121 894659988 141672599 6013639 562733578 380682048 87124174 407536567 93532596 511395801 356081994 529031623 320539128 739001222 127956894 179186486 548390637 272706714 342101572 112471271 736218271 710088497 434570871 739628506 284363522 795833603 962078209 722643332 527459321 285791726 176595249 770590441 32968066 318267848 629120432 595701643 698949895 568760957 3238210 792482490 80156757 211836555 321514112 253212236 950837776 301987357 284915073 351744764 427210422 627016644 316732387 163428693 189621493 751303257 903057198 473985014 399653211 717651758 49144697 927112531 3443483 225739946 550219323 36411548 544007793 179339754 484629543 242957687 748100711 340384104 35440176 680773819 404737010 209470639 786502407 208091138 363974348 71417479 559835901 791184769 698434123 876568287 954613461 888055615 480387895 710187010 214556980 880041105 280355119 263701676 659669987 136314954 489441621 62405662 25242853 33449413 241745415 362388747 128923451 842362477 702772850 16879978 375652648 107509860 78866969 162155054 168117349 442841316 86088884 727953249 234026084 784523006 604521536 41155897 525094972 84909430 603859258 592168303 817466887 884214377 855869979 329653225 873045682 197827951 392058886 898288534 83793716 486320653 113193633 65233518 328683129 815966482 82113496 704335776 775992693 160980464 719007181 944110041 603821779 805096065 524579642 690364214 442135422 129101177 731520110 967230394 66526958 187895720 411915048 736510196 72110096 120301378 918679773 797672129 318129329 163255010 548477014 254439396 649575662 661670646 319672913 978258791 330153480 401786408 535110918 106146172 415283223 106634451 902772565 19105001 911730515 279868558 561985567 353865936 261486086 146022028 173612681 180529395 333917747 585527729 917039591 258544194 705829106 688235715 56216322 876474786 851490724 604693336 130914181 501066386 118880333 450587094 331841528 449033812 704889853 719468797 407696336 120173076 826103247 162985252 991794428 737833761 442853809 553779994 944216049 704339894 699802022 117828729 884869288 33719768 555872809 654425230 144780314 114218267 342660944 200996635 990693052 46668020 658206322 974123585 547734405 777086655 277227030 732092284 226120466 982116882 451561080 633816801 102289957 130180679 796802052 946600737 868014439 92172212 352897082 664746839 796512105 52699103 635091920 681381393 938935223 43481080 188322974 83715536 157699346 530983918 137228522 908750 577651937 795434844 975032334 977902693 425037850 104775715 709994976 651158315 86892596 14072407 137491468 41698905 144253085 786809871 988299641 864783876 878982083 193713074 529530714 675494187 98928529 17138985 209391931 37863751 60620065 397714905 974095638 218319410 781215174 963840511 71744511 211383462 611791706 46776844 189286154 36829555 4068910 751797481 540504222 90961506 765869887 677995689 132660410 762639324 317321911 973476402 627423199 196303993 19705827 9470264 724314532 118634355 26609249 933706462 9014457 87229313 183937718 983110094 158065074 965152891 799466957 229809585 29052704 411258662 129102780 218338857 300604569 133171690 970136337 841108790 224133195 588522576 371620830 209309956 203678251 688942740 35302709 831101449 885246733 55008535 693088064 462077616 173642890 719697312 248300429 182657346 659442976 432238147 18283792 817508050 249907389 817750748 47317634 278960093 81525761 176420413 349815301 382130329 309592102 172467990 75755470 386241648 760990565 447376299 595551603 964668815 136319039 483370663 648286615 874082123 538379198 193891030 336159738 564538439 913588342 584460166 747195784 425547669 869214664 617995927 243055718 119122053 288263026 142889703 250598497 369788787 319310116 600413797 604435467 481418569 772881786 680190937 867660217 386388702 127567235 315728171 203573868 116402625 799098834 704376834 990484747 189994383 898267864 179160836 754532821 664372557 763621002 354244956 89920225 485352017 972240883 185492295 456990421 260503908 328381997 707588917 482809046 647692112 160519066 87244513 129110681 785917203 767435449 849287249 24822257 747519035 165015419 228396124 863921660 964114252 932772958 854406406 6624986 683557173 33567242 761157806 347929729 649704595 115402762 290366305 135056611 87643644 475858599 444563384 200663903 804240596 4668652 683472949 304449059 165187717 623233813 286076091 951104920 243185613 135363339 975927176 990704647 152895110 56839651 854626306 117009361 842128960 561549064 123634347 525686132 447632657 737308504 726132212 949853603 852711265 16498517 937426565 792871260 492357115 381989948 846051515 149114062 386658600 382040815 453563121 404362668 5274627 739639211 207983939 248460239 875002550 36427466 91681237 27897659 93267117 946307543 997423371 935396076 360372958 973574069 313598560 660521966 563398925 39730771 610375568 268626541 908745639 400318484 61497801 253619106 782308432 760065667 402733167 21483383 142106481 856296287 425846050 147381107 595935498 633829989 248357697 323454399 670257454 340038933 203868409 616040922 138862827 53808131 403953350 351752136 879898552 717551909 12274101 443297476 609799031 475166020 711924016 371061022 875484504 625938168 624680127 510309287 238520186 27413293 531792669 380626666 883709580 810155070 380524124 332161429 296501410 481398172 508132179 966758864 821437105 712000587 435316137 812816283 618325069 839269486 164568419 498223620 409337746 29358871 794037447 19136777 504524891 358477815 242714150 380009394 984415982 867394276 890318680 75452520 894807568 274627700 456079185 631033499 84782769 689119661 815711279 233800531 170517832 323843457 53075746 844471288 888360395 488391882 657287571 506685464 327661368 674372341 857425435 736999113 703731211 651462882 608652241 208256101 9940696 851366390 440781846 846873029 571277017 183616877 922325548 318600937 458244576 230921085 949634435 395543697 920040745 617862066 629344227 943074928 941705522 682419972 787546216 682582269 23328205 297350138 41784084 350989572 971722478 899209518 940505037 527970040 403188751 401673629 736226141 265645798 105556371 29524338 112518827 676833387 213141215 887360726 995434323 671385790 970798162 797585110 919445838 743355258 415447175 401306416 686430186 209669048 83726387 326492753 892251316 107054592 476359242 934035399 310560515 300598071 685761269 103581903 828568110 88950019 505255532 417310602 354595817 610811902 446834940 319630995 287645288 659976154 59508072 135595963 183878295 30306234 933181072 103324133 626177843 201144598 504630548 165124380 410813645 440873287 491617132 155581313 400444230 967976373 942133063 563521096 121090795 627894331 667102999 949658905 569360702 172358530 366969506 923956518 783170431 813804445 96103864 923332070 326296950 8128287 58928032 510175245 38434520 992109103 613499377 517128715 45770052 970646276 682253094 456583697 264035914 26386578 464681361 664480143 994362950 406814423 80517591 115453745 887225106 747620589 917629001 456585807 919979118 137114858 233058676 555665900 950919303 181678891 331514321 129732604 189807177 390442353 639907848 80758049 235067807 105923576 597886763 280837859 76569852 280139856 589937907 340605765 306526433 54619267 857602260 153405735 313950041 938119850 121375831 201175146 685740438 39004831 510277304 458235907 28636040 743335979 866418158 979555342 925014869 197932478 109287946 114822046 440891182 601712145 48096446 675958989 707635721 645983208 809313199 784205572 926123063 399251105 977327688 85165848 306386723 834929947 91087934 620336763 625566148 212463764 821511909 163822937 103984946 184305564 622058843 132620985 927641543 340993352 964692679 705172763 538925830 926496976 672511160 979817011 528209120 720607605 508292351 88361192 219107164 170121901 872566763 145230227 569373005 702410803 82912426 875759727 389857101 174000359 348612842 15423249 238980474 22641102 179246185 342965419 206946665 653821380 328102755 134588207 994814731 292795433 692277322 386256912 71808760 217304833 218590275 600017880 790428790 726882625 688379071 9535953 897004526 413462186 7282531 318893882 115872988 90194956 47169961 358246440 116711666 395782802 373669688 355692139 418423903 405432225 551173909 625370567 59253604 879276664 612475126 54068334 24588448 157268799 292841598 96397208 227089983 511431872 696415087 17518772 90830848 237310509 27054725 987835373 503289046 886853607 159245607 471678385 829564915 58931919 829924825 946276580 454714720 56110864 154485071 725654974 461543088 705658979 203541892 520796691 437451994 816017017 427381377 462040442 825802167 720222974 558437649 52892150 84171197 107369087 70410921 175002044 344679595 949981997 15353769 847968641 689351956 174599375 172163377 518916870 233531293 2088201 317709801 540762364 58199065 324711223 266417337 519742152 30370202 469959228 893055195 320338547 138492597 172952923 782378988 964294763 893175896 340816636 869703264 977347092 448185722 792630537 4865487 645381669 595128885 20219255 345866661 284480840 194818629 518030037 655914061 280866273 520118238 973623862 821628636 430833654 150851436 88045972 950575805 33737989 410521552 696147351 354076536 401530500 869100273 136455523 218341614 614792520 329788511 88044878 444655963 777974232 880675414 449521450 275872252 328320650 469740704 621738912 612801490 664559333 139768949 121231902 945425605 512403538 94855763 619570593 943237191 98223551 560132916 746329347 131961539 970654467 442476698 486038074 224701318 164093322 622493597 443042932 778885842 952282107 531087809 223541804 582772690 264279574 673063253 858644942 592600223 142803957 332900205 57918064 659879641 472669153 179149966 457821597 985072690 126522080 77392189 780826232 224745630 490041457 527155579 356707169 313212275 822148628 842745242 537913593 986241949 317755190 980956524 765127790 122553648 364560684 841185946 557842690 628840257 366765550 269003983 73956831 362085858 601904187 131874895 21965498 74573340 163541212 332303447 912162381 142579643 262211987 545504965 367325273 752253443 72660543 576548793 65465718 747325522 271810386 455895662 733567470 589565576 436852185 351211612 564635575 801412868 44913909 122478264 282769476 411679458 391482246 209242658 773765316 993386433 193633904 648247165 920476124 357175115 980550611 685154856 499754758 95278950 83176172 719596382 700048744 8353066 296145174 618030813 755678587 567955559 73926474 341762409 10037486 363295010 692974020 574673061 17224229 737887928 549667676 299993704 2083737 941149922 509236362 775849052 787052706 702870265 424096217 560045181 912561732 257163179 97716388 264832841 204958480 180892560 984429222 905007224 189245625 133090747 523038036 944924212 701046305 449480862 139202972 563600143 812775871 832176991 138273203 830000100 422581270 540457230 129993803 424665006 334123503 491746516 53030410 121176208 47133133 477126626 533737740 959694864 586806156 483970480 77044056 791764636 664863039 61473277 696771859 706625015 194564023 72326246 504065578 748126679 521807107 643268549 311726821 187099330 327961891 302516375 17099429 750543160 842973605 999609583 27724518 29613459 343872451 80754927 3306019 391005583 410397904 537043758 203216798 997204059 21014237 280260853 788968694 538393627 194250481 338256904 97534994 388814503 263099502 601600571 136941181 784906608 244869120 301184354 972005937 572831010 456217080 841621717 175890522 151707036 841231300 56131391 181320495 37620102 136886317 184626513 428625684 547284220 721670270 484358833 397004630 595200859 764619685 38489676 986110837 958870165 376746579 83645830 200201019 639846080 685246401 189658551 277269040 782631872 343359256 101791328 207979233 799576336 943413045 383869754 951283371 637160696 440001144 132603865 674780797 429403812 317230377 955922832 976688031 891416999 440281664 226209013 339134209 57417700 264698688 325245045 868804216 641445266 261407227 69005234 133807698 946653627 111180136 263593089 581801850 454539392 365384416 789781082 106632079 161313812 26167188 57915449 650990859 466168331 43035666 178288007 895572143 360266042 134210838 724776525 104199392 427008853 950985537 443333600 484426552 68200576 768578645 205747119 709645842 29985871 127268704 695969891 829155849 238448840 959562979 263474050 545504583 177463746 53255131 652136661 338777558 79422318 710052109 989768416 398107001 753087774 20572775 146195495 965870168 154783612 870972019 70069559 581792465 674473908 513403159 918735368 742674483 134498155 124482487 304836676 17000377 251751190 806566 698672577 342716381 812885896 962146626 888220963 990349642 15401756 540357623 181643551 947340426 102926084 23928318 345447426 708530209 44501092 491642920 674400376 199284704 215131290 596986287 633593520 742121549 110389445 552328887 337312384 97403951 529327725 642149059 114404327 781078915 495471977 665593255 123795295 160874224 627739880 864532610 151223865 495657987 257406584 332867415 295514764 360332667 356795733 640962189 68862876 401296824 985121460 595779603 453097879 52769102 45282241 86691398 794890650 8188037 491536637 132203033 105591987 20864361 626868444 72512665 654459627 122340420 738105919 630771274 135730995 218362150 495303883 286954860 566536489 752710466 472338626 862051252 965559485 829134358 355529793 886938712 82947534 340651252 335234666 536045412 393420353 380516907 475253162 40827355 388704943 966789798 173030387 494296930 987654158 799898830 419325946 494630137 774755601 9948217 125401410 910486596 228310366 473221644 49957807 794846854 78448461 522296432 509414458 44007945 203947142 864944250 930946656 139411027 58111853 118697674 675456438 451532206 499214580 3225951 492359560 887919522 970015748 517906298 234732803 810186258 170321480 654058749 304816394 945077080 664006965 282734155 708080027 892317330 755955798 610554185 539680536 834404258 132850617 49094993 878412203 189314110 766555594 661875210 328725136 824667446 780572883 856697925 128716003 132303814 859923876 621075562 20223336 829939623 138981860 254956138 492642232 161819691 909014886 797458625 106896770 425538202 80192779 667493149 170371884 688664928 130563685 710052419 523069186 115930653 611663763 253997740 305244762 230735708 768389301 486486249 55403153 401478536 343184174 184119156 533782349 55624401 657711069 554005684 885564023 649209280 661478174 230722607 811028970 423009411 28181231 770442092 848547613 960890362 290451592 18919496 502071641 421015276 581488266 25140826 536945929 45668380 131654917 842190690 276404087 900044218 181193291 331807239 154039105 524377464 368442746 687821453 580001864 26153815 94343489 318082238 675363094 755821662 548804844 338908416 178831072 429502427 109350507 27378684 242909140 399802098 898814531 744980780 820817373 480302796 622637958 210279653 525971175 606809226 52470343 802375261 359369795 86179985 986698852 513408899 610557448 355141597 201230352 43075663 233811763 295573840 213674252 909174857 51395501 762479096 100599624 82742924 44497874 209950130 962637960 139923365 462268579 861452490 884904144 135602303 194271638 360058453 345881956 572759164 966867679 250868650 227650777 178753825 337048634 214349628 692162724 947606081 422007576 893393075 843198095 655819339 41483266 56872346 417510547 945395118 671867793 518110170 28138041 716365666 728060299 843292352 856289030 42845229 557261194 593709526 178447531 751532831 806284330 524329486 176808346 625668360 775198135 404459122 804422185 112246768 618808749 496584908 912369200 40816325 242494334 755567294 549152015 136493951 664955992 966662561 81889068 336823784 484772730 962543460 905705802 65349380 805835812 614511183 108194608 215613357 60737060 286642138 967146187 867021390 810971624 143954532 492689749 438686110 400930006 149628285 550932878 19738754 646213192 315818429 913071430 741223877 71385723 314739796 877717827 588858066 281402356 959606894 925681849 618691437 774666706 683904002 684040816 433018869 298415185 644751775 648632225 359152244 931393913 468294763 78689985 594881888 464765646 571379734 33567997 865695651 721008018 437017226 737950757 219737562 752835655 503538538 960961438 676737729 818278334 691195617 118112146 99680689 503318862 43793994 570888478 277985567 580214348 107445645 711004435 878629532 752197420 212153011 90298127 536107684 680447773 168988112 130989571 145213419 592884197 17073919 10909069 166408566 306607497 601376177 386146127 911959503 104914715 199623917 441213583 923193048 890819533 559325728 875390088 246654746 455636073 298794917 524640313 35850420 406240562 88161099 766996303 158437981 300314110 857294430 694545664 980761882 878798893 678051586 978491652 471683089 547641856 841917073 638091654 706765704 443293249 876754133 618725206 400724315 76378049 59938788 176433714 819713933 471780867 51823802 66368678 927416940 203135070 443525342 963267359 609375631 384202793 582780014 767813611 684516902 292590795 314875626 517795135 171389687 845443563 348803139 495589127 245601771 190720211 133680780 952367474 486529811 862951264 423609032 887254126 791845664 336064171 63687839 464075948 807845038 968027992 382960978 735261977 171163062 826486319 551045687 780538692 63205463 133825700 400868655 747722364 278932846 568260632 118033851 450322532 413704195 466836989 945911658 659305965 510073551 932108790 464189790 996603361 647576405 887798821 883857486 439422069 223862992 800061677 903498016 31708029 768089668 138975345 619486357 791769081 965461664 23048395 424824125 28667126 9390447 825692779 628905842 288323292 246469762 599456044 591162176 660173956 66293032 389590185 171996272 428882934 174215326 636186062 425486294 821791731 376501234 161860132 113730151 600364225 961921808 17228166 484588605 582527827 8719863 956591313 226813260 974181526 979639708 651637384 855365003 841546506 329846514 336787196 129869797 576316275 936243239 573548324 89006583 855052622 963138509 261002854 136451907 137353834 749705267 561938201 959145564 126206501 576314684 72875714 579087077 390752843 942620232 63675682 973280669 951340094 872783346 52610280 778037971 704939405 704247663 485919325 546485910 34094176 675222873 528872059 610410451 463982463 102420382 699417033 171551437 918075242 812936238 308003343 55429076 562641505 869941543 867090991 541364357 298772578 792483057 120451433 689525420 587619640 36643466 515322441 391476085 909426812 567932720 22030407 466882568 272180383 360466083 13368478 158790910 35688955 394756888 769201360 499671418 349693621 321134744 671222854 120285215 134070982 979226196 28230642 549228838 701684091 895321632 90593194 456668 540321040 63560978 542498440 980457031 100204444 57820880 224449467 862147607 625753599 246479873 181546526 750450333 606945956 47431355 909241243 495151262 442188242 530958954 994822679 644398215 852093698 518561884 764683429 838681031 350304432 792914070 240426220 904504874 540752053 183535765 757477893 81073093 99613094 299976332 914046475 52333889 210313563 138495942 914481495 836067162 237492166 96028021 439033846 844438121 143459375 348275088 192105735 438163969 879234042 39444765 82562183 583844091 558006649 699761963 275041473 760827432 492676032 367984044 665332305 33428084 551519808 275326549 967017528 651132901 575302881 733580355 703466790 785616443 872076296 470464636 474199956 109568461 419009008 913233802 806522934 414984735 114025241 998628668 705665055 845775634 38073432 640743589 282136076 448596432 340505551 557177548 61940215 685697934 925161591 727272519 571642369 329197750 2599068 391176249 832847003 430418300 124756603 388830144 68551094 849349250 859294779 395267402 811434062 130820139 161017555 470473347 398321225 275042795 321618366 103986279 120818429 212208150 744729867 255470856 660804581 937751769 812648404 722744796 623449702 590326346 302533666 47608422 772040448 157649085 438784670 604887450 440583736 563541272 993717593 509134830 265406873 705528723 904402231 76840935 688865213 65419785 547314281 87186437 192978931 868932647 43689067 166313711 81140796 788418933 421784567 594461728 578687053 86949322 169722875 54653106 529792019 324772893 102261528 301832466 482421977 541046197 759236267 923005713 104587469 605470211 284656894 222510693 163515286 41575476 299351627 852380498 959511612 699182260 939566935 5006894 420631258 983256001 171320605 354288405 624191286 445621523 948750132 55394690 532570844 970989359 110047796 62362862 295762251 212309323 216711680 630700579 753355519 975947946 406222643 710459339 433934509 690879536 932970032 597449794 584971363 84838010 449830291 544482974 784020269 241913577 549489868 204651526 77685930 573326824 558939930 554393567 18948346 360206414 609788256 404035541 183712124 719836051 318914754 479474374 932145373 535626433 110174952 685500892 364090731 368913947 248476582 798025239 59793482 181446613 247991384 497281197 266284623 697821674 41764170 50304891 792251603 443770389 107472769 869937532 17097212 518929050 276847450 888561909 879135463 886635705 292597449 62847586 606471756 611512203 394838311 391133480 999654987 357529615 76634371 216262069 726443561 177627305 14287307 638753394 359073917 114795042 136034590 477874891 812616716 30315112 380696134 457384670 326601852 488168902 179838553 196215416 7097951 456686002 84777324 738749766 343321706 229891125 654113703 802309813 693919679 901468366 193443293 693574665 111514332 122594015 909836734 837957892 300221319 776640392 329227637 511811588 891435434 317778579 989686478 556568501 200610042 370382611 13953170 379728245 711067864 46308074 575943660 570682167 502994075 513237336 161948284 846315780 595644812 816061986 501141945 289564490 570046703 694585237 835655506 681561034 669695603 598008591 372035277 969916922 227165335 701262914 334244861 118600768 871557844 323931338 527685620 72167885 546830301 394155141 304412481 257898164 440463214 880356141 828580330 943457288 246109828 990528613 642289419 841754639 659106951 143431363 983835480 81670005 690532951 819490985 763231039 212744906 270015928 135266315 35178179 497181262 689045580 369423039 468298381 560603423 693354376 995984000 485287659 92701028 242655492 789700140 350599192 535635057 522572632 31695873 331608696 621198811 874740838 973898114 315469801 386364140 969845829 299305280 468034144 512895131 971312616 231265182 725640036 241328543 219047849 760818214 738509804 908093428 130241252 59324536 321213203 676111980 55308535 806500861 768813007 150480378 448717352 971928550 686115434 823806335 3624423 17724129 445005145 730881612 844138595 760474945 117245751 666500775 912296576 585279894 31912257 883609192 669061428 610068645 977454086 888109276 223403210 568480242 796202703 206160814 627804777 117415905 882272793 535629664 776433118 503602151 686110041 77666821 328047053 224741827 901473156 184187827 94982307 198994652 915069438 791637253 811985949 32315188 310654379 724282524 470111433 342566636 460408067 139172860 952635280 290378505 879798487 28554841 858858746 528517542 234715654 486663522 498449798 116988446 22293185 127399267 473106949 560919578 205066088 801154001 638177756 959055595 985341827 733160062 10566598 752927616 377313667 822552546 637759155 687968045 399351422 107870587 30534680 859759488 99559799 835686311 2654344 831874637 864241152 861513089 360392178 98956805 200692963 858841976 68461603 75502499 986241242 394084903 636422076 43823681 47755255 127116183 2879275 885613433 860276245 13445873 638541048 90106263 688514770 128816554 778074307 87866191 89203492 661125339 800142031 41279642 349328001 802796374 873154279 66085504 664309463 86062808 17558661 865002425 944904783 86020263 940504923 783662377 332621517 429443351 680002409 232893123 556559533 535398036 118506555 269352129 401360260 609563954 359458391 89875029 738380507 137532698 30257572 827583998 651174388 830399602 868863640 502388 633195975 742017918 66587892 150021789 828080725 84146552 867540565 625501860 22683166 660561840 261680588 207821034 90005190 941682996 440714156 499081074 329597383 559220710 620949555 730957642 21301015 980407945 820832671 759681521 970456994 851090242 587265518 474147733 534006195 308645509 474650121 19718521 50663426 393754364 169740310 731260503 477900915 37280874 209278714 353100432 550359065 323475653 560921465 492880606 117675000 1635620 991961680 447272383 413372681 465427586 178230024 434673695 298351882 851579046 194355215 121325228 555185639 634137084 595472960 89191833 942782593 70123080 108910354 845962370 316393795 131167015 429739224 794294709 20964240 639017937 147395140 571323305 962493589 560832956 64203910 80168589 562468575 908681941 379957323 975841255 374109526 558187346 263031301 672461408 262282744 457386515 793786635 817468382 91523599 241775946 906660215 886822543 164415378 868086920 732784912 480809172 999253934 15040488 127620233 20218173 654058424 127531724 591541477 469068365 688364680 508261739 401753305 103349606 416943679 781710627 79190861 643569557 192414324 194738513 168547316 454697067 652125028 962333950 124681801 596164978 56626247 31342015 335503872 221041624 751945286 68288783 701850796 751199219 83329270 829471028 623933743 589904046 957002751 67991572 911488762 645367430 576253310 165758418 748717036 993196988 947469044 680424248 489282896 992399719 875162760 657830211 299613138 379804139 472680512 424294938 828485468 529306759 308153304 163989339 750348382 60098589 84794474 452199177 663814159 20640095 134186556 287747901 463060492 91189307 355739472 374549253 589073088 931992781 540307670 190306475 777706121 340293065 870730722 119505368 185209136 598409834 777335579 484822273 830730324 250016090 909117210 659215792 779322848 217270513 675721482 382187582 129885453 760515955 834386758 793699611 633672402 968573314 81447511 96732893 912278972 289703335 323798498 501352059 74212467 864106167 691658534 704434939 56915584 414905607 823940307 242124719 865831792 601275885 726946991 696562116 703808326 488580552 208294259 335647526 705851064 884015740 717835107 835736516 497048047 404738216 481952478 130720448 225827881 415916340 79969692 138106852 705619674 403768189 491975263 632348493 120390708 36150148 336783431 29822643 451055754 13240089 271947361 169403898 614515973 851410703 865966013 170840651 339991254 926776623 506488176 898358669 663308714 224323282 586611536 12873112 629061497 68564013 143593559 854889378 484480352 76079603 845512581 42616378 332364143 337487843 674964870 452754850 373637990 864264652 482577492 677210096 877504741 607041204 846613993 344537065 458451906 565096357 515377715 650959511 491872979 21865890 549318179 7698044 98705523 135929714 20571156 727767020 57010078 16681066 435172749 394006782 92760668 133201681 436623159 425124811 470689524 964104380 730396012 696843865 828369031 65489856 374053960 558390123 672531059 73184304 902927188 130982965 638280660 418304902 634458827 130153638 292687144 36293358 137851682 391392666 24739423 10939189 119159685 81749501 27620254 406848785 475756282 120380922 540050466 764895792 398022084 863256341 729000171 128418095 560100205 409885553 193907950 786670517 968275676 866439009 859854820 723719215 849938325 498135480 142024116 336913503 480805469 287227611 373206860 471173502 678620277 397946283 482112690 650296313 479695783 509732944 57145098 807968416 482630217 449711915 572864207 880652300 165484607 154380729 9070394 725584811 416782633 55494696 364771679 237574660 774450056 224626499 961293874 476904732 575278330 955834342 813818234 56083798 243061952 187025094 379773652 921682228 584971376 714402693 424494893 917183510 76651988 334156342 725151925 559282204 783868256 150532483 439934503 949352862 157429563 301521249 527454024 574212195 209532296 892225703 811786855 983982351 969368553 773080728 460887082 544646882 581431421 127221667 453247031 824493373 314246760 685537034 598691952 751734487 399939727 23186844 668917996 476591714 209859537 246586272 35873918 993727792 249635106 328324772 795597005 407064668 482362372 175567381 981276863 691894667 920309435 793063717 675877017 889677987 418660796 989280450 286841220 92217 116502117 592604602 677101941 283265228 278141636 128310244 34999715 530597714 4013440 556434062 7189427 213872976 803020334 895579696 60117120 52655439 76420820 708230476 312236459 558783191 883797856 293513321 103194210 656623642 939093389 779071226 398817980 210270536 620868028 685659199 62879104 737370144 130780153 739981044 20635371 408921788 720807640 908151437 939519501 724821079 464585499 799225279 791210406 120122184 547321327 851327525 25293974 476258498 412074353 337530432 35041688 148388560 483560104 138235897 805012202 422653492 769823475 203830181 632924028 243207854 742005732 695803131 980577997 872785884 288300527 853729719 134224023 9108166 614397508 73743523 586445596 78983006 725485153 230172353 51621541 125322831 81499878 76915514 601581328 346090582 266962298 489139368 494479141 750522401 479891616 299491342 25692245 102231442 355837875 511132624 345439295 97843606 59452106 178533643 970629489 347752632 884779714 104853511 209377149 499177221 31113385 648339096 430676578 609114889 878511449 334814470 586954072 812527678 264246335 41051751 158618259 531208632 530191118 653097399 134247385 862599086 805105093 12455981 964830527 160942967 523588604 162786174 111302924 583040709 193836168 81932412 930793341 78615881 39302274 992686841 430309453 922932010 641025937 860986030 384563250 372053737 48316851 971517321 184581414 312563186 12569072 195716024 843771817 395276541 848813422 830535553 110391978 506434866 842991533 75222505 667377832 366580136 90525030 778680755 949620845 284361197 713129518 732930537 215493430 604948143 578133729 645802882 380396504 71676017 359305264 617476106 443729753 407622114 441509778 628311166 720185299 306595201 824027189 416473468 701871742 525356963 247009020 812263719 31791828 90000553 740002575 551686012 309097040 683043956 182883118 111234236 967405153 748528988 696681124 35414934 205993482 274814853 681217815 586389986 346490869 40523078 56382443 790220622 448145192 497892220 271048139 20846842 804487421 947591680 437320309 358875514 325464994 684329329 23655584 209773173 626846233 763658159 761459184 788459624 299218466 796858654 899693860 119139970 545387641 448891335 154554903 751381122 723706187 835772718 190287459 922713408 876295795 246669901 565450381 176957338 744562121 836498519 197804180 401565893 636606550 635124488 760441406 962071543 171970168 784096989 171844716 651332752 400271499 785820251 439792376 699489965 582678904 192002587 818629934 980582896 640893921 973184837 584480370 217116460 808957554 774767828 139829867 537769700 873954081 557796599 567243390 471032553 246811469 765047569 872598445 883418019 252688408 633039850 845489561 277174928 269653190 869850628 928507679 669924689 655670879 220816406 369414653 90866134 412818992 40560938 71449030 906229265 13745774 508445751 123345724 675219679 135729930 115691942 65505731 9684010 526004892 632749120 480716562 772816360 250313040 205831358 656234378 503001447 838871207 354240291 780176374 108524397 76607270 561200405 630965437 732278148 782016810 380089 675660634 47352154 40941026 599626015 953581418 907203152 108071765 929443493 582422830 243801694 897651786 647928560 106002056 423656677 133194031 586718617 48989388 383507070 792549975 705223766 886508517 483937533 911980408 519201242 444978281 988587677 80401646 75943717 573382177 714934808 928840157 249042810 762286961 822297535 848668824 715868378 582017038 809256940 497828222 16956219 53058633 395480007 664884779 11577040 671653035 798078809 598295657 720642422 34102231 243361983 278382539 920610747 579815867 190362946 292328340 24794148 31466975 225246338 953254216 604849151 940181145 734610725 853891960 554984457 409424611 555077135 123369186 991441648 216850426 621197407 8397866 122425410 16677413 525798996 134002450 540846799 176394157 732298106 261489220 210496387 828176440 539871759 983623485 407992306 582751056 128468176 285302805 614218030 353714513 91073373 219067180 146412009 678200449 925475491 701396465 87625059 333068977 824765650 931583058 549919402 298479408 792497275 672344812 167673172 170812623 806347261 708519970 199723131 391161718 970009190 410219517 219338157 362397300 246359353 479846814 945148355 374827528 765149619 411882737 728542041 708739343 630949916 727470401 386939791 408941759 281383218 327081201 742010735 106148867 111180610 291930137 257144627 756194236 964274948 424817798 927006858 623138560 133337768 126729988 14300277 955863309 389465856 86154785 170776960 635825208 566001598 115925314 10652736 183667568 380324402 591711128 892406910 11274318 171697880 131863052 272732428 453081097 458944252 14743162 411746316 422641213 159189650 668890942 178835449 123464597 93708739 958358658 599119508 79562858 937604998 613419784 35426166 179587205 699574568 206203125 815412413 118092518 174644791 678581500 301760085 554969192 122808979 194166995 418759861 294506858 326030046 691492288 747587955 637490650 558751802 11850622 60131862 717941451 680741563 91483662 693922400 774450301 49842320 293041907 854013159 987447317 758978043 741955676 19550873 311068962 948158801 834963285 429161479 975319943 366061136 730921564 382805486 341386466 925088558 801565347 635893324 103634955 345573986 235997630 741125604 904325787 247848251 653773818 474783590 928589813 745257479 168705989 555556465 795099798 314264247 262085975 635063466 73242289 4041651 654614339 384311251 804716803 342093975 813472729 632553097 560671463 396910644 15358582 902057928 174515553 669440280 390467603 278150508 15014266 626465232 871792463 771856404 726829834 525566280 99156345 507935998 123340111 267862333 63492463 918439908 582126580 178094789 406019726 507885220 34652791 913150416 892196470 691885945 107760742 558185551 324439041 668432204 955096194 192313975 570490132 129611747 861754254 960957734 260278606 729284871 439939318 132071068 353657627 19285503 510153700 452813971 527221501 633493810 720676304 443230315 404450069 155319235 621325103 662986146 663204454 508494246 576136561 407917276 200380190 683897303 818619178 377335583 204845858 626231723 569649557 775335989 608359821 431403810 588810075 868638426 13205033 881265744 853225846 366862659 900551246 215895897 819676629 427772746 701906058 392869284 871003060 106356126 548188518 344844515 621858624 63909324 853338760 50511536 324342951 906235301 734408838 142962128 283570883 939254696 769193850 853220439 567107036 230070023 137140601 8433462 98708448 150345633 889699205 804450645 517208291 642766803 872862893 189401271 70539548 574768950 582270555 794058960 533641428 130459072 991419826 8016403 46884747 697274937 58527938 371227697 603510237 792936776 366706176 739597472 584707823 135900026 445334262 4331210 218486400 582474862 12764672 169711199 585336846 754980228 974161844 102545136 250263382 699541088 144462759 173319282 126826390 726733313 967378241 660467817 709708736 811314418 668484219 756593483 508589354 727012156 980337531 964615942 372465283 347043707 704213413 809689457 335460084 2064027 814020667 553946483 584538888 679301690 723657681 22392086 286798269 550335876 124937221 537061651 102393316 121916331 710380932 229219705 848649643 530275524 889687521 558358379 194106293 410688091 167468213 702695646 990216598 322095 519827939 215198233 347365801 76557704 24887689 535342236 78621730 691424707 89288718 663160617 223242748 665462751 685552702 510041017 68314978 663006275 899619019 170708293 784922605 462516302 399927997 486088600 992791825 142131869 44446978 39414469 405336311 64431542 742110114 395552909 64753636 114454404 610751141 264635789 191012107 488155181 799978024 269633836 179579888 741783094 932794453 402822635 259762196 470863506 765380003 328077173 986386132 664999021 351301818 623825089 127515322 751229814 109913688 972823498 745878035 6877017 12237966 151214345 71308558 606864431 399283605 988578545 721318835 10034745 253214333 912330941 350706278 53192357 34481129 530286165 647491802 967275581 785625151 907253997 290655438 551005154 87847521 129557922 68520526 439149338 753383010 48552200 42895504 863296697 873892049 788773538 722690065 738646367 939987882 646514974 198027149 191787839 635093518 919345983 54338935 740824203 684193276 405045212 646532911 718674404 935331376 294024712 538466336 573472879 53795060 681638125 124478032 141642580 811196046 45514909 580791918 564579055 94067108 623687421 280392103 820475509 412460958 3082167 559121875 204965191 502113492 757149023 396753029 137207010 529011358 451091964 730547564 65720985 856137175 377080474 636911740 643984903 523621537 27894427 69974133 577416596 709532551 46968516 719059175 520728597 92483424 299851092 937824003 39066884 923538512 70732458 859542392 188515821 73814624 271180618 245997364 428444468 880845992 642750392 418167829 262373701 946358707 148715392 328094685 655012234 378312217 965006424 151513488 901933753 992900850 221487620 479350348 554949753 268456135 50925874 75678349 360939558 350776966 866018703 252522793 126831829 936751160 112065184 167864002 863082136 235762153 413861365 291526603 116608145 56611756 709694431 231498197 855486815 710926174 559592882 510499048 89238390 377115657 662012535 991172142 222532859 883500154 323038841 777482611 4472640 373964714 705677311 365412197 577258031 424212365 617934990 704089860 360963525 582516525 871953861 76562012 670795030 138331577 368088614 639919526 47459684 930299396 871417722 902946498 641225569 283526955 265961897 582980310 660642612 927974431 426668803 735691822 663990936 749707643 365690784 668463575 976188708 71368094 886392124 553446739 348096810 356843465 110052950 709060334 939359989 834523162 785622345 462671370 972854738 6227310 102590895 20314421 936526705 974008617 923260919 430268625 110051923 41739167 13248934 770694534 969713598 292434088 358902707 486220885 42141730 724593490 7200812 870846790 648477935 893592935 276809880 996574745 102952751 386862829 558151430 42312739 73902342 196290127 357500461 46757079 202517436 460091355 67071499 991560493 286616323 842848769 274345469 396668246 884587936 140110755 19879131 706817885 432544842 378781838 45555121 327202924 103375327 52755932 198049713 604369614 798865218 474859592 600944358 901817968 714238772 11612139 796647059 788141113 207902265 6663871 834898191 410419701 466755225 754486041 254496545 605887900 449851162 528842013 2556145 186955449 668952767 874951627 746289685 101497609 106249816 791844805 428700532 62141495 697117089 479266596 666511108 348498658 954126187 119971817 102832978 520881310 131583955 751996388 309022422 339486220 758660258 996436964 749905920 77931834 603439356 4402464 683819733 53290517 385760828 538892229 92762317 54713595 413843856 839052001 8727555 520093671 483413158 437428086 582235165 33046598 916694681 101262624 234061607 723337219 221234440 336894584 96734880 352818395 88890971 405757301 692304614 700067580 254710616 294726885 777999414 858149971 151645700 461819146 763956840 537406527 711375 856719156 592120121 267071582 548287509 600847675 639681604 884217018 890792112 74433121 917263615 660003144 175695744 3841573 235856714 396930184 340736157 332591593 749748578 282143479 738348893 442053191 982211059 993059508 736780075 612726824 703725831 888425774 74545969 467682670 278348652 927773695 176918177 870468773 47361628 577722037 323832799 687043232 461939054 67141263 761476352 231719020 727144406 937172095 235560593 963001120 186618630 428813101 295592712 936367207 710956579 886457957 230936749 545683989 732033816 967716823 10927164 435759646 708658948 85473133 755958667 987007600 865763179 932876844 709992724 765641159 363115232 886341874 305200742 825054286 953483136 66677093 909289657 680627542 856365539 144850249 496145013 42984169 426179701 791737724 831867727 137136280 530712032 62804476 535336620 262745848 883037650 546263784 551021845 444212950 484253268 306980512 283736901 202532798 92373707 993729624 968173956 455488938 732587849 125891049 133059575 686070985 45084493 42349232 219214878 901450032 39715832 715359890 796950552 318411885 359613965 481334630 308064516 890325997 544139105 843401135 5588196 279693107 242181270 556610040 723906056 578950889 716106903 7642956 781483687 808480609 853888931 602173994 116485899 586476779 728065043 102061825 125064115 773149535 144411056 196795344 527115918 36643240 912155233 176582821 207571476 124285550 657917451 515635991 867127898 54572907 211553477 872716093 334266013 453734747 281842484 58172068 32685635 997949387 918331375 666685673 658946347 772220305 121376019 627948597 211213436 701957413 730010422 188793902 327623299 726937829 385589246 854739217 616097420 150260830 883838389 823668895 274546379 394272191 339304885 141674276 448845098 550858362 866906720 635627462 857109460 1265556 546315882 742311446 851731294 464647256 261513471 363193992 89383913 382889489 991142589 153113700 84846901 721153010 341907601 264986551 300607190 727496846 119725767 916704610 877757676 856080508 740373504 4820406 250352698 932194741 146494682 551714147 335569454 865917753 187341609 192678913 719699660 733657490 934990358 571430953 50821097 49020180 934624945 140205009 431909668 778283885 145835060 369272920 351953246 487742661 634259471 652560435 215239506 606501589 569265044 92997181 315098448 162154900 97817587 565451146 94349640 96828620 117165292 282435445 815262724 157023252 475114357 387478736 743197093 262621066 958909688 794018190 311641246 746050984 786739550 596067265 376851220 932574610 965340185 728804465 272833622 452116007 381364900 488073127 911133947 803146295 433586660 226232395 965301194 383920598 644199892 912167185 333265569 613881535 47118981 1044644 770904787 522233337 388523379 366618231 637370755 199949419 13152772 949012000 798516754 799892322 397595616 175367974 584983283 215452152 904172438 857816904 667568158 138053689 198406382 431218457 941199984 484509393 657450851 759017529 868429990 154167094 523701066 54211910 768048628 570820046 55256554 391469766 945569735 296296284 758087997 582940489 348762054 771240768 384468840 147278808 423649441 782064455 175163133 8632723 997516607 79335570 718965978 517601116 69905611 769888712 948819572 863621946 254398104 458786774 475155826 975344446 612953867 998856891 29556355 233518847 422193289 937329260 624988612 220279375 86141896 383076608 803219863 434903949 6833728 40205054 434699108 430483168 674785860 609862240 291632243 524818818 541714162 10598220 42419934 611619772 633003283 843755857 327758069 887401387 155058983 802913894 715262184 620529201 654287137 597334890 854048047 76480425 387180502 479036659 149276151 473322397 714629618 952496013 760742697 721463345 845217418 195441805 151946513 520003277 805304044 443578755 44822095 199534557 306693326 939758380 811154328 939696609 636030588 138912396 679614347 643605922 794342642 247392882 264135123 448629778 844727771 118183169 377626554 231908272 449736179 526902704 557747020 16882149 331915068 318489717 738345493 29648837 366447873 890292005 549652113 24268268 186387111 446990559 223802825 345596789 239265290 34957152 137809749 727812230 26385900 817424095 371418151 673244893 64816976 488069625 121874670 762061098 458769146 352017575 993969370 908505324 731436630 404232741 925387472 63351697 722722457 516249317 93000533 89170329 259057673 495168997 113438597 445444784 794675908 189757773 791041572 33941197 77231276 928851320 614269778 103617175 598791766 985687929 629378419 516125093 326273905 603769440 130702542 785043050 955787014 124671911 546064726 539739995 381421004 323968549 455608043 104143460 840217865 401124927 45830141 99275538 896293924 11785089 397236673 543486183 54059213 40794596 429943731 131290488 969645915 44213509 87424015 420954032 882417789 716802433 789595476 208691693 320571873 920298017 993734743 128875238 897486280 392315820 668615233 278907283 716284368 124223275 235567094 556502233 377864554 133913586 508294122 126674829 998215026 905530794 670161011 52274238 946325389 100104741 183564726 768487655 144318249 270988740 41958038 879252389 987791172 831553513 87944082 160879396 751851529 934195176 142270986 501854160 179027347 810886218 780761442 895311714 787625844 868844888 304330298 18006749 2758473 812624419 144681577 853489851 718155212 814842587 905764088 516996952 914947328 941845165 285484606 911781928 65350256 327442643 643550669 53141428 11512507 584011102 66537175 763364036 370722629 208808160 117734547 549749975 872210729 898495989 445061688 512352925 619857228 749391986 530359673 475132052 414532756 675041250 328621902 132687968 489883836 86902342 502201271 257347515 28747506 787685877 21645795 94097762 967644871 665196463 999755541 979157378 101723916 918809067 595037765 472446544 127617227 712772311 22196518 852344307 463784651 319774557 364697231 83641878 69166542 895056904 558773930 336215650 422614505 739912183 321419969 912498340 826814524 823621239 22362207 708078382 463823467 44008001 654692495 431468338 561720815 506964387 263142067 663444730 278289805 858179831 135891273 258423383 570952141 10604142 110767690 34736792 330378698 327981272 970895021 252061592 75554527 382185302 588277241 498169031 122097485 909697209 263183723 801428360 585834799 285545929 362023093 49658266 182070281 16715587 333642955 596307447 376196325 596785021 112268528 654486130 454964851 100676152 912909512 878433343 111280293 876193553 765686486 294175342 204174825 736581507 546236933 279729351 118766808 987030525 777898382 93380644 749244085 41082104 894809004 335078884 179144384 109348448 237253501 213731016 126064035 570896455 810038462 354776711 167681475 922306989 861779192 475162677 22983140 627205056 353596019 134263432 503398608 119282505 280955125 560089784 708380363 827192058 839819135 679663522 666738934 470233868 625560518 415983019 363832323 372885873 603578254 395493058 482234320 840831754 609224073 460814706 411728208 419262534 815591417 431926034 194085874 529886960 907088710 217069013 157092015 113201080 203848796 513006975 84999936 484803920 73096758 793380298 164512329 765432244 325560172 831251263 88182463 951120689 99750633 452014785 176522913 703328886 847507842 658757232 396676991 309248266 119571938 808405198 728510799 787679706 92847583 922596672 317566665 999936292 992182036 327175032 113137371 48547183 840182006 198137307 533351103 913278763 844033956 550379783 531227359 22110479 234147397 619409821 973231167 333898029 71424606 2270431 889743266 771448799 661027663 286420256 80697065 780599600 947341805 661724215 420795657 40189387 436837239 738362321 40125678 281535626 65537352 5779401 330082809 758235709 56433059 863433911 524030824 900467014 266330045 55258182 922577493 500477442 674668002 748325011 834375470 598608959 750595442 576635088 222574110 411623104 863055343 155787526 44739055 662913500 670028092 465534711 703102886 106865330 56413383 595744916 240917308 974467087 454040668 571000116 732702795 510473726 286950378 109249970 410940739 553280422 164508151 186034583 53757863 691692505 934359594 740649685 142817815 684955035 317284772 365391924 949094490 32856466 373695801 993833544 695769965 43723893 311884606 251389203 3105574 220814340 699650470 244022881 195281426 153691137 815022996 780500573 664164862 101973373 889750542 927621952 507770147 54258693 113656535 561528009 598467549 48016128 154694045 741285363 585487514 471978816 106677287 387098355 357351634 332889439 233448250 53121598 376613331 545332855 157027152 232235257 766147194 856677621 476258137 813944972 862885109 143797485 594445544 379566322 98287209 336712437 307188274 606057355 243487481 273361160 20101716 841955029 173893639 174795760 583240392 759381152 499290928 542434030 146479506 856642561 875323468 232444107 762280510 104453151 777776961 919307662 336688407 396440506 628501634 665462895 62901829 343903095 809260379 657347372 723469416 760063940 994059809 30657689 218637646 90063641 156535200 238739361 932018670 330428838 266051473 367775413 89809989 765342400 910209442 88805846 621984960 638049261 173766304 236781821 595018763 951543264 8605834 931707169 200500122 637107468 449686416 263401950 981010562 111463146 773265674 556996329 871527085 619841834 440170370 90164731 709905474 596705569 181420443 641924143 927134407 447471915 9699555 869460747 212814314 772425348 810782945 687315625 262990961 984549248 924097446 858009723 788608864 932703279 642233244 989108985 422327098 91919659 105027286 255854011 55899156 878292959 812850340 927426241 350651144 253020709 17590971 60556618 849726277 51527765 554997112 629377035 498999680 417213019 498837782 711813993 42154718 162137078 251645970 305145678 146686325 175743415 15671753 935295188 108446693 510421348 776920524 383290143 454857358 734464162 639144153 510756513 465273472 451994492 438182753 815924616 557531552 308290075 876481233 259774181 359817840 283994696 889151215 858817519 701207714 240505348 423147863 743362432 402642425 674793832 48508109 549328750 703053598 916696213 337140289 664016643 427117560 966577165 47306785 881974917 701041326 686450937 245247782 18831149 990961781 683430534 834755764 548493332 844236961 563753348 808267512 56571152 847748044 549935079 915388670 548955757 790440426 191052884 144834540 193082851 718363068 45859001 594927952 421416665 962555213 932068240 85433307 242189125 751161756 985256443 124164041 304719433 524223732 221928174 323550582 515185512 905358708 158306345 916195195 602112020 722059693 576979059 658683171 422324088 126914137 426588192 971279844 917354562 617641075 116114384 962953764 188520494 14489736 557881715 609937159 977044948 342466307 547886817 219234072 93628062 385659612 195914465 250863847 909883343 417842638 574414428 277585206 175717697 732720772 193780400 777829716 307296816 770759458 289029238 729620903 750189946 715617429 553417099 520060860 185774856 522047834 483014623 374295349 536537569 893412690 984232507 366098868 88395348 384635676 585332940 34539761 770295287 633763756 285403607 532694981 51606393 859818034 810280186 79840442 445055158 4060585 710186509 752351973 627336395 999215747 334489228 230042692 714833175 740422678 750103551 900608030 114986863 85634526 127419731 651524431 979047215 111652237 17623298 67442562 348804264 455472589 101982322 971615902 89236344 387385929 504310882 993359089 99720314 167107419 925715882 544775471 23684356 635902390 149643796 651020750 487634488 484133023 881063441 54984015 77072052 483683344 955592044 192058914 569317869 83011774 843583344 548365083 47180363 713722993 468323996 248500978 21711934 570306317 72633232 963464629 810208597 576944113 809340069 909928911 744051532 735055950 454704381 767735887 223474692 604348176 271272988 711109179 940997550 4852780 766093193 18069601 488536123 574201589 210128514 57853991 509729714 906228209 458735425 409426428 472467554 927059420 510443758 494179487 349882089 583076989 310160467 12607037 12537453 119500536 922535947 756588984 707072837 229756680 376841222 930547528 834104855 500630561 494173059 627618757 505483341 112782603 645688357 846535815 539500543 708333223 756906158 49230257 614561431 68157934 311173036 87028984 995217354 821616793 433724822 197615794 257210133 743885289 210222830 269747586 715902176 132758777 26336569 422975012 215031808 255694143 206038892 49136662 756324703 552728302 529271770 114324395 665510904 27476479 960860210 57527799 735809701 570282719 106758055 202887483 638440652 270447442 142432819 486174357 944580587 576157640 683790150 201790719 172559280 746529332 471538304 888461455 731804460 350391225 163952819 946836267 458601719 222508062 848489280 67442773 775236363 377761050 181767168 293263618 405237528 995143729 350791416 141047228 565426447 310065822 196451062 56383450 580513264 338883880 542557807 377610202 915041520 78864308 579400920 940117151 825393639 903455576 681094958 557198098 106363152 845047776 356550716 564964870 67555837 205039996 632407642 695308551 435317397 814174809 988572168 840554924 661834889 339363584 834118503 79777687 649429405 30569564 136161137 82459020 221969796 678718943 460069221 137011315 757583250 891986493 929644817 582976889 795442068 610739774 992691338 901805219 308303901 349242054 319286440 228376089 406798401 951694081 923684639 842115797 618385242 764773159 535187072 280220130 104136742 221821926 359997817 606082498 104907841 496158953 541057870 326877636 27394247 1127090 316405302 784977496 745629934 246050119 220470736 393588353 709306244 213162074 147909923 17610145 414920479 467196362 98502585 821718879 418890443 874703576 663834675 37275684 639476734 51538098 170012165 596129827 273360023 382526333 54728676 378267863 878685285 595786545 705145499 906079531 449429987 21550800 543573379 47576272 120117270 764044114 441164625 829423514 977206187 589074547 699550010 244643017 56270909 798052594 66361895 327677703 525272521 582712921 217469738 17265606 634251018 387481902 613395432 907611040 770008235 520640460 285878903 501209871 116427004 991024401 259805754 418373342 865091552 803379132 465949614 985208822 419939597 907114238 814632335 249662136 348705136 366698696 494305152 404976044 17267641 560667047 732653746 542540162 143379967 950123483 559805767 630147337 190121737 25717551 537758376 812646323 546358010 676153630 166372545 515301365 519694382 426178298 933674707 384785934 82073781 252140672 222511107 502013378 11771261 37143441 751675513 360476396 256358488 98497016 617968792 273626128 659164062 203138889 816166289 655060381 5778724 375972056 137724069 195900460 401689606 675482444 8546782 948047615 204152426 27435678 315865331 723846807 453613976 102056389 108632740 388204108 354197060 183660198 890217485 218484672 73319990 494409349 578961068 329678477 592906365 49446211 603304605 104586778 252585099 419470893 612163510 258363822 647959300 749887578 454264281 49648905 277886374 315327414 850212871 482038799 342763092 18594554 205885605 648893419 120650942 167034697 37097526 474848002 350694894 779831363 693332673 424014884 126757063 124810092 753693360 719663427 174256302 209514316 676766557 426841401 628985209 288930066 685205222 129460860 38817644 991985855 31626117 169220369 159829620 881838987 651259167 502592711 900433540 857144771 4002481 21084482 876695819 41100007 348448835 79907065 820931369 894297859 503921948 947688431 19107951 110131659 519868210 45880604 319645975 49151118 325238356 801147535 338081183 10443578 930608394 229415178 854945784 962234510 398635546 14775403 696589849 49894712 369884466 449539740 759555835 373886946 323140573 488768005 414986952 671589407 568675069 88434672 418403618 72597016 888639455 290027920 35245027 261024016 335908523 207407353 310175133 661146879 8554887 648256315 524106808 939163280 730187845 231568943 753914142 128823390 246344345 450503990 31234454 616228810 900043729 643306640 990115756 75700654 132074644 257619059 747290060 553266065 198570083 18210029 478379432 87209537 308237948 513624458 348233552 644146471 721031810 658408684 157809701 582103048 159181350 534432860 373782680 889369194 766001802 127696821 870708936 12346146 430717162 754459741 481091308 183277242 250282732 323723415 258977895 234873727 433858825 6267955 788139791 632428907 24477983 119035575 719638443 185232283 632660032 920388346 829378753 206208194 431313381 839704805 788311241 590494731 374137664 14610272 332380276 140139465 142307092 55605563 5001962 573024253 662581655 338609621 756301495 912864386 514849387 15279389 254465 948708212 874063695 640910607 581137118 751058030 759946181 153291913 936290312 245122565 73680258 618185416 451330758 357509991 310406572 92158350 948004721 684544235 106768622 132901348 677200051 101592065 41023263 534718364 674616318 703604917 725844337 283434164 468985655 240693723 151229904 469240119 41918286 877809951 110150725 623055404 481384332 722613258 628863668 270190995 967735822 555060277 888376410 271582931 912570267 51299333 363741280 713091339 735843567 323026253 845992687 265559969 424618318 887015949 652794684 99234635 443137217 378639020 235185150 912122871 471849095 238931405 233879341 513767380 116741355 196546418 136822783 598125686 919159675 618202802 868316680 886895496 173263079 609209441 10994778 85833345 660508773 374736057 651441036 248868691 697762310 349950074 366945011 122380627 89482374 19739695 74131613 532619590 250895066 161833114 444742461 722744160 400764518 678621801 236511540 370022225 875168218 225850674 968147910 646844244 844053476 688980942 386256091 869832906 150706734 397250868 808182602 663731859 771986925 459623637 912600549 322265586 809573710 132061912 297162564 899056083 151801606 223810528 284192025 402696671 238159993 728934485 125440831 638924510 260072637 214468722 8946734 987757207 292835747 829610996 634601450 136889222 371108289 20857541 859238479 374331374 270624760 667421081 38063232 42611684 979561069 803180133 217393621 641651131 935242044 367072536 393223565 87043649 590883063 677415589 342256671 829043055 258866425 320213853 320483917 518939062 387198926 181947002 359212620 680034673 864074349 993814069 669440246 87698989 867187961 528678725 462030363 137812721 48616157 500093594 32940756 28177225 155790078 102850729 522344707 91032121 469923264 915568272 30592121 913322679 592983860 225365144 594882085 851850285 545578996 915366001 223305698 932777922 949829355 582518317 465328946 813903703 428848737 134769191 901602692 148553050 515964267 216149406 138882122 564580423 716242999 24339229 445274000 872033077 127189957 967618706 815581549 449629573 735703329 846173670 215468603 181203541 71538813 810350687 33053825 469634160 578233040 108875874 254928433 528062394 543910542 720257378 194482448 972759278 707542921 948601491 973828679 223507187 164750896 112710800 640603962 733510247 989566381 85877961 458059675 969272689 906013018 273641223 271418613 494232699 972331244 486887215 675436239 896386408 297237902 561006415 218536920 875470941 669882288 473465352 256049686 66309181 46239082 303048485 39068458 753782002 251649976 865413489 829805540 268917223 830640640 470409501 2427469 820207020 408803813 460487143 641996061 167333183 586644718 913414673 661565881 558975961 400301888 189518471 307878721 550056141 750524885 526415640 278043433 272923524 999880991 534093118 339232704 898636424 837141602 230817513 504934777 941307929 96231001 334740317 210225152 926871641 657666169 65168972 599595012 66469982 525656115 94107424 86319516 112300832 7522097 600401748 523793144 260340336 789920218 831671864 810396476 540445102 210603855 88439908 813368625 63001198 475049377 5117680 961637621 164707330 235935192 466572398 106015259 332166193 653829066 168756762 111554185 311495234 233925733 563665548 230481567 759581847 657772972 169317434 724399030 665295068 769719181 100708526 925635403 559639398 784896741 588548230 952600851 995500596 676988137 618485827 58501793 4553865 623603506 20139413 169261194 859538698 339228162 275276452 44221242 993057227 444033213 155775426 157068813 677958946 719440973 240066731 290057144 229730296 409384165 866972526 895025363 179103345 967681051 673177117 591259095 605094143 114241698 543859945 600594738 791229834 14862124 511612882 795783698 638465629 384268647 965044892 498004326 723496808 92837695 542225567 569070387 389387260 550517344 578655551 67346205 122474669 818722281 209919700 352204964 228106445 76892225 99746679 259726142 897089627 772923795 850985236 354700122 887165493 247361532 955294859 530911678 262223655 319424093 179211728 900689284 703692739 996772971 251209961 279705898 89610665 793435528 848776284 331514276 196469223 279948186 251376832 318943891 98670467 461296532 671148855 179293263 390705108 770895533 439019404 140311087 396335679 290004639 495011208 136017523 537366171 302822418 666929201 799589825 622246510 698657280 552795460 178455600 695430250 804005421 458161498 637557266 449957300 159454133 969071542 646426522 439402319 72964725 965370413 538072785 534261256 636519267 717366047 777482716 259931151 8901803 917793802 656266829 298906441 265321361 792284352 688788963 420660130 311729904 340895140 42906640 10387183 893690599 73878591 558333784 697696019 532040088 48407401 169670 691494221 17478942 646596192 130896539 90443667 611966604 521485675 477221274 101002222 91368073 107220341 360933372 100269875 25014142 17200200 399176316 142851854 662000903 87965278 563511984 973730806 281376769 458934975 984117988 175067368 532813565 394968123 725279738 64853653 443375524 725449408 608864225 313370817 372045599 739760763 256330835 836528554 113762789 733552109 937530775 205130861 840772449 150980498 305400736 718302943 20697049 704577051 713671148 682697952 645058680 129699483 508945109 926435449 588634457 345579449 954019168 973964374 740547571 679298905 891334378 183923094 257264664 500198602 497293911 629310262 92475716 753624745 318355167 206238504 339693205 108402293 411369364 32982006 259382790 716770099 603801300 132596191 273863501 317472447 815294142 771438533 447171930 176755602 550390333 888322738 522335050 504409500 862287111 262882621 36224756 606137840 299322066 293489420 106336441 796615976 775316033 51328508 402757073 93671200 110083363 594966629 202073492 521452727 627948634 313972634 90739177 84266285 446568824 217119030 401738732 114379317 988557562 701427013 291134918 538947894 589749750 813469968 895873745 304553213 76352588 932098500 910691052 228191005 78104271 869543845 24806981 853420304 773388704 280080405 799607855 883472067 875047033 1681346 257441145 355512019 168170331 348180321 439778303 614739154 565299350 694033386 729118470 406373263 395460398 20253388 945321156 837726500 833723355 693711252 142279712 762592294 478326104 905487115 990783298 556430374 627547311 868106630 262367029 253452367 703386 61974883 136924433 728266771 916172581 394365577 83778789 84342911 595062249 376073443 551598417 12877951 70106829 280716886 419251213 318083578 153486625 217088721 8326429 987209979 910799972 3122492 602318624 389126075 908609607 445618274 798072801 388673269 166241255 60439829 642125635 19460993 974931064 631566419 747727763 743619996 25931995 684022903 680479258 473510596 60096345 84594026 486388546 982719525 365310912 905639758 153319455 518797536 122728478 161645883 358523867 33528450 164768375 813358842 275170876 925894333 111493467 73243676 167083953 277734722 986199857 809209588 297195714 813647272 293292358 44923476 409783619 171740705 581462730 942779228 645251300 494075426 27373254 131639845 329311303 245200517 37279602 482630757 763998052 12524432 496792991 975038270 898569233 661561365 788397112 26256460 439972049 899890578 99500136 607056002 30141651 938216344 268781941 179853716 604379967 562074298 77293543 866679937 733815002 658756272 809459164 379066301 152831698 689348769 363222497 482143000 934549285 253018451 817290108 551063689 265542882 314083098 526101958 16628466 828160815 167015421 42884925 268132863 919422351 142385060 875188864 949564001 933117755 143970804 129417717 390014073 558561454 59227611 109210361 292376455 717983883 918669525 523959108 870815580 460534645 887181604 205474931 395083930 140200054 22765038 946147618 258259287 189364487 324765927 274887752 17525301 344297700 317772677 138174516 263720050 312674088 865879731 65800402 98308195 862366887 47734470 488322267 420928340 106962081 597532628 565821146 824945963 368718504 89780253 548277894 829253148 976961857 606269176 76853429 969678262 481550565 875517398 227937549 670915051 52799677 502825300 540956704 397097376 820597976 531647571 660817425 133272064 397527301 579134178 84096610 112410539 626868648 572418876 533338878 586347080 22467855 99160024 263809394 243702710 41456628 812087287 72955858 870934836 270872814 2325638 840613098 752423378 877843036 921066998 275854780 930642712 276408649 816811483 180256439 97006625 200975405 841073863 82795040 598502706 272724392 19408001 710913244 899593039 591826876 96768474 338456470 466811083 48444849 602265863 710513792 89901476 266869501 635986001 813352664 537742314 638311639 506482113 290165691 368671026 427549110 566020471 151830089 703957758 235348305 332086527 653480734 436323710 25676741 588792125 887342767 298401132 608200125 450772362 50510523 52543353 547540835 388966992 519354435 448502035 991232855 82384578 390919863 110618707 718370579 204272526 648361021 209198569 710754638 938526711 577869594 990820099 357063533 582216034 547294208 444928190 914302560 53291294 881251899 792495652 642083418 621111017 90896783 102799895 71883378 993923657 7859599 471940565 235407001 527214033 920442599 79156207 609598610 311362461 189774913 180485540 368151338 838135933 389684108 78905975 629178996 967553701 922242425 986242528 402286086 469536633 283687069 169104997 522827926 17455319 961600648 17427695 638566335 905013783 120227589 710449713 898937439 128087187 34906629 134344439 507817571 955349227 66016997 969932533 119228040 255791910 150418072 487379377 93927842 540102180 418801704 723106837 360172232 341044128 561865717 762458318 663097112 845552785 931563314 38441389 863008104 745680314 55869084 354090790 650694096 28613024 64540502 402147886 9216563 99447130 389008677 369550485 907312709 455025673 339483017 26540748 710817582 342417441 513920124 657261776 882519620 932721827 232884964 95208203 126282307 794750680 710182872 789379418 492819817 494262538 827820807 208344272 239942851 736206242 562435061 743153298 764819265 479491915 145301183 626552179 431455396 386826211 996102664 191284456 694368236 188102032 217825203 257702169 530519472 584261679 914963944 265555443 369499857 147848908 360763646 495782163 795115939 70946517 137677933 140452107 417725406 818015091 348796378 657668256 554221332 763747791 253337905 171556948 95756057 251155440 798109127 527211452 637981650 646728142 718495908 184866237 834830173 788837462 442568406 365349645 373099140 357532349 630905087 742598997 357897608 844185084 90897511 153013547 767647953 81091795 293465653 185373358 899106885 494778383 695557966 305844568 258526173 948895870 477401516 354282229 200051309 128026994 734010032 690549311 774755135 305022291 875415547 462101659 93859753 317983952 827451303 319475244 528032653 310872742 62074240 885930260 7574177 5488103 38943806 775222129 86579897 184925811 960595487 985686782 679704193 508669804 144047701 790746717 457565673 621449216 145028945 510133334 601992561 731555328 200682644 229264047 36577619 76098190 691365706 130437371 246598494 371333360 302428966 774631146 682206101 217019558 513077757 689780278 222507660 404537915 317518758 161603908 589463725 130630596 147290689 121684269 639300399 143854742 912430985 96866072 765303957 909976281 459515757 219812870 494047960 660198400 449076916 530625578 588812941 140442621 513579300 687927786 511775981 816008266 315075283 46498433 33027823 828153040 588795062 108051834 232690954 906313820 269655741 674671030 36944415 269462782 796355298 676244814 413317523 561302634 625627237 31137831 323795266 85142993 250950700 817843225 597857744 700027616 200985155 39187036 692986588 567080806 727114822 57278920 235605423 42190104 103777353 121149597 722859495 692572414 229201430 955550448 451402585 351373523 482737829 488347000 620836304 131609478 17108165 886670178 692912111 495251753 917808008 869223728 432911097 21275060 539583305 30768840 573819027 740568459 922472227 266805614 160165616 502103400 324084534 395771039 396809856 280378238 516920635 119669350 972950651 746122065 927736150 276869588 97495587 410473978 765216587 570848242 542083456 634841103 310034771 87511918 130092855 80359130 956735646 563003951 101634189 348835302 446289142 675453215 89403760 221277720 794775181 102085727 723381120 118859714 497856765 120190975 251754303 14777400 92376676 77221305 613415816 20112825 354090892 563427754 283103155 119307478 134275995 825186610 606664932 296827117 765214879 736757786 377186246 574466876 152278088 478820435 923302177 451083581 6790001 865222288 672361301 801565181 967308015 395742420 772941246 465164779 368449746 24695548 332458530 460826421 101916853 945874345 480939246 308524096 509302098 764042400 280347926 496094444 441745361 887012857 792921560 59476591 476286995 22624158 633943467 628565082 501444592 557245643 79648663 360750944 274984283 604526315 14832477 242292297 268734 787773722 559973427 221234831 664985622 892431957 682061251 619418826 838306301 15516848 927942921 200124751 779559247 60807198 548735546 73820959 947820055 194173458 133297550 424107049 216797615 767241016 905188482 718242206 177003010 837353496 78993149 451987292 441879810 93825625 546795940 294664895 734115699 106769367 515899725 251617672 999201323 50477328 723552849 690023975 65994175 504012121 742665077 845553422 564819319 291400623 771890732 512639373 485574080 905188281 789262773 702371694 524945648 694451254 273130251 554465010 384321102 204639751 6452301 826200911 150981728 405764593 973382158 737613778 512533959 341798234 989231449 364251633 392275561 565300649 906791959 458269736 69312769 649457036 156339509 634132087 793374010 928230240 999287811 131464441 685934873 788550583 833836134 63396872 335518189 959482736 617861881 719839290 16638838 476830534 398556552 167620565 882595126 224455061 905234342 247645436 566253295 746982142 611897068 958528855 164799142 371205378 416798590 234111911 20662413 573138098 720760349 666552774 353884690 720048160 798017214 39819562 361115094 484369699 103216433 549149634 443852434 721078314 121505275 460491272 50425199 520061827 480628188 933020324 744516887 238378882 180665759 163286533 985361023 645079178 121815388 2676517 16284555 391130329 236788427 889463320 964268427 957548775 556016093 170669468 530113286 206549659 210489029 743744732 690919357 166221813 292894365 134771791 887300126 414399640 447779414 937725324 786977818 928407601 723261999 384011056 19302834 903927757 547297589 4663857 401523286 669112976 7340373 417807841 60243304 96645151 159787512 877028082 906710277 715803604 47697549 289339915 922353262 110702929 33084646 465788971 276924742 178495362 453077113 16741219 592895001 900856526 806982895 232389170 681780478 530244893 616400226 701083312 286689002 163697814 558263520 688212287 685327141 418120244 958536479 598086796 367281746 118323990 327631230 273992022 686643946 227845130 563331936 461513559 338548059 448932933 927302529 467989152 627428295 380379641 484730370 72839647 133752518 144229616 305228817 668049348 674474509 921629042 221649011 813679862 85326855 779912530 354408500 623170347 50549125 312944979 221257142 417830870 283785320 548888371 544339243 970429265 776733501 107671179 431942824 967797911 409120463 211761704 435787062 36548757 592141345 773033783 109388404 578410214 917263399 414617220 246459561 444254259 188762613 468108571 257934120 126605819 100537452 612342619 749776165 3602928 777803949 971033306 421433797 61589269 372438029 965773040 32018533 1687881 925960570 316477708 969485791 187597384 528239412 257789204 224146141 972897108 30822986 186050896 551307321 800602736 600668115 650283234 244856994 789430727 118391804 355307465 916036545 71445608 967650084 518329061 75048535 597970384 341878718 348998684 659559652 714316746 167288075 544094537 568520978 93248644 713088596 390523120 133362379 93844359 648312323 357508519 66741466 531651661 543559414 470565139 184770748 996743880 120848372 429627742 638690958 91756527 784935206 407243854 15718486 605101641 925572914 90767021 55588377 267451632 439765704 715148028 834284729 607053778 111758916 402805707 552818773 824847512 793328826 686181151 918691870 294157501 896206022 837949688 678325513 292281787 308514826 863096260 289025667 281879549 145240353 927716624 373636075 930175559 187476830 389354561 387793551 113049743 332637933 443381927 233017726 772403636 11046307 67302455 231973765 122805222 322624513 637308889 800169085 115953338 176006391 571377307 262627190 72212412 261843346 940952702 364494199 570358171 656565314 506036217 852237719 801805666 286269192 78390145 584497576 473746021 320261057 972291127 586795764 652898989 268189405 819813489 277818976 131752063 739632295 509792740 107073637 62256807 147101628 907242721 30726497 175624371 331136379 145870038 247836782 592979724 86822740 464847332 15854246 595904405 970883548 720608316 397710070 257152740 798998461 982207646 730898760 119259517 807015124 170210875 624674858 927720880 842540716 902493833 59472943 582173010 264802925 166546579 496946169 264420904 926305651 527672665 440045274 109958382 673542702 687882056 702938105 612881793 5245739 571308703 61302549 976129287 291917018 459012619 85798378 943431830 293736616 816697137 915207699 953268091 839424364 539882556 880988970 681965079 294892740 792978264 116654440 559695664 959524842 613600608 824116568 738346845 993789624 264161841 848305226 519848678 804560248 403759682 132730470 809805987 975068384 46549371 785935273 119501754 505561989 871733650 62933583 651814956 540947138 978141281 605083046 232887853 370540188 338588367 914852931 665432928 131566631 884023723 77644943 943607824 350140682 901761510 534471020 343930306 18439703 382776245 863778983 822999950 786535927 849025804 632805936 614120662 895575174 271257560 733622415 253653514 995507561 796555998 905468469 388971051 627213630 363067866 621858903 850270170 554172585 389228186 368219449 538255567 273251908 445864391 334379742 623392589 347625901 868850762 819839246 366065603 104143358 536134580 41581904 890679284 237676736 674387840 357316298 133251909 798161751 90938712 239421775 793669312 740011061 997406595 35156714 219741043 212990813 657015616 70011212 767163397 46243801 438230660 305418963 172012060 884095050 639798704 795404649 84237302 361165817 467760246 302819256 465309175 3894826 344401160 208504810 241571561 18788999 565821107 227339821 669467101 656759819 319277947 315652764 249287231 316684542 350809477 469028273 529675354 7825093 539039484 149355102 54068893 829786495 454774064 78597305 566397897 947089119 874001953 650635198 308254936 194278550 953454454 773564110 198173375 150371965 982068919 292261287 21677315 400406378 519601108 691144415 57166196 838879054 6797179 158969778 8079947 357606655 627998051 390271652 217948099 19553886 539626753 124533344 849340381 994400816 203130648 415738277 794006287 77132600 918889826 102261222 123927501 724860631 728341683 322100876 875232595 562926953 614362162 896909909 963333330 986479621 588054324 873015877 677875027 447367854 31985655 685954973 804974508 512500057 76226625 22922607 532053942 468369729 147455950 381394322 315286897 203102949 649648950 109293183 132751900 568538776 64070756 256679400 145915758 644928790 578780275 21148353 60372094 45658789 918058261 23705424 32138409 358628936 749237652 562529787 805996789 633739658 101001112 463487649 146239714 29744088 338926607 530810008 498113816 338898908 912204329 813400712 542001856 414369631 922693894 674753755 982908406 839281001 931433154 128824163 484209790 362729781 2488867 544581884 260904921 773063480 420803659 145559681 131692415 22557662 708089468 790205556 508813672 809090579 106209556 507569737 838834666 297652514 38379744 336948481 636551421 803100425 2865545 31069628 217470055 925559438 558339734 52894812 617356791 342289239 34235326 101566580 705019019 36724193 498664815 965923939 662304024 771984825 111483620 646512790 794542487 672089439 289234697 155872510 481180017 395444252 663442246 172531034 693096765 701821990 509479514 182164537 357438766 512345058 65750516 574908820 290420848 624090249 480319983 907777638 966379488 514555308 861860569 523914858 403795852 213041736 342355149 66099875 985026560 306355120 565129017 632085398 978444558 854363713 787957907 312140926 102324317 303916505 484671959 795421081 5738494 994151472 830101970 215693611 359012882 895852485 790602430 501950081 519942734 123438764 262244070 338838573 637994071 124104638 862753430 894306275 189662725 205108578 812922501 27205637 511463697 378051517 511807386 342424606 84931582 152281645 654565531 187255898 456198149 139237489 982676978 314452994 985905313 665295299 530146604 197434546 561147784 173265385 699384626 933606869 296704148 961628695 272445441 934698218 938249684 135198870 681520844 127912409 192823800 494443345 7634397 556803848 725011213 519441782 899228454 809942794 671723426 553793984 997198691 127921574 545547825 832392021 294890919 531453137 497687319 825037522 728887682 911351454 998302906 280788659 844958322 295007053 242417353 969920114 82221623 33183388 957635336 763742466 13612148 2975487 110702162 21246544 559779334 835713375 393204678 459007787 498172520 64928103 865318123 495371211 45366029 410865947 180279583 192773299 794835435 677966901 17810821 376239468 441834707 16113726 657028126 139309380 163637131 899445478 109229494 98375105 932628865 66864829 862117570 946241013 69840315 825336084 820003908 482136000 513565810 213208585 941143787 11738329 130653040 658978261 359625891 28535420 69844207 539905473 221308718 717195993 70388726 91635890 93435460 512223432 107749616 750463585 651532811 123903098 502425414 760762304 222278202 287570630 680143484 936912123 86327994 602500150 762248206 906331902 84636150 128330367 972056838 878296288 140068696 102709877 389790900 499694586 983761648 312151458 39600059 57586718 29347450 109988784 149222607 122782909 474728567 109488574 725762845 126261377 233391671 80704610 739540033 308186224 220791591 272199868 245098347 307119585 874700018 859862904 65967838 811852519 988193271 38024675 542665158 128261966 993250904 932456057 480472903 829528903 97123866 372589313 887115620 126471315 335094448 36338227 101770575 809823014 145826800 680049771 788600743 231734823 760754380 528140775 539921046 981545970 800340642 785019392 141181906 527557011 497398648 59666095 191925881 485591918 97690770 587107390 466370235 943458025 372079798 799359489 625503279 469203663 24465154 512618899 595674977 359559601 401473477 549961903 21898967 547300276 230011673 810499709 779035098 843282404 191156835 171472496 677344726 844013828 956491887 818526631 224087191 306406886 878192726 416013071 791998803 828399847 3120461 110885389 624374223 227716610 910244878 102393853 696920273 934710031 615012751 145111601 146785983 16486227 695073504 21201301 416302855 925085176 831701009 47854304 620883932 875374195 219326799 298228657 719388023 28335038 969271639 943475213 334741923 699980716 212004635 979257078 380896914 67641447 90142466 5271136 295358057 852903695 107664989 992278329 640130077 575194091 137389929 639432412 444196670 684979784 660633712 713015876 462581312 344851073 760870179 83465243 220225267 832713330 234210251 792129641 861048367 203481889 588121205 48306641 903462605 800125840 27563718 136875870 720283638 970222536 142147006 15641694 675642582 102328346 860436374 168289011 530038788 850342655 807721422 826751809 387838790 320871485 539767684 850420101 665722557 153154215 933885343 885947824 985867544 20611945 530593816 699432262 224093834 118715021 600255254 980072790 771357212 480335324 116948659 491640849 303074211 111612016 359798895 978716792 66456713 72751620 999522154 449011853 775610626 659759927 275763661 163449416 980631412 668047697 13869516 646353968 821201911 800271211 384818143 659585806 820883155 915411959 211534419 897493340 886643331 811789672 877566129 658000542 144641347 847031140 2157742 447715557 958643155 214472988 278948701 877616220 287224608 278470854 326628072 62835233 938230781 454908084 78801000 771378544 122955780 945186868 270248863 796674042 597974430 655067006 308776199 271373936 422995316 520310617 168867276 162154998 184616641 898949756 820155539 329257987 745980895 674829632 776973544 557140402 889302620 55922244 287272973 29043579 186909449 613901044 91878811 977656581 68809127 23196163 749035124 44281259 968383030 19283987 840955300 418873811 526867344 2247851 690247746 802379011 522558467 859115021 964534008 559691459 610581129 637205898 888949446 209078375 312035529 518439341 766218776 53854500 426877936 53491748 82898078 466303736 519909143 27293241 443960317 441234622 50489403 45511792 338032232 871388784 917312130 31503883 290262594 296695825 33751733 980510339 99074835 556310200 692141712 63608842 116001658 155239192 553331091 857467455 364317566 865366620 228423147 130536342 919221119 507817434 36544441 2119197 974121170 408969936 29412437 270597838 702720909 932418191 316109629 40753140 803806974 85938111 72257022 946585919 382633935 106008755 779612609 481708770 514835306 324270672 397833963 483353315 479509863 951165054 193337122 843827429 669048025 421760268 826880122 440785495 929577702 715940914 295421043 756215223 124910849 177349831 26813060 680148109 109768021 195439040 720901248 766091346 281377150 645674622 565193616 664011085 751683376 344806225 145719854 119035033 669076896 396070168 602388347 1103111 199751573 795725468 844930539 721315949 70002088 671810660 14617796 999579789 240267925 310038838 608311363 217695126 339905021 635124422 897843234 302189393 830563461 471260834 68280739 111940611 116935455 485990706 628468047 721135182 830796930 626704252 840170214 352390178 22774419 442558560 353493288 75042344 90800380 50940178 796358292 160802467 722750837 810976087 12898607 963018761 973531277 621209969 33230238 313436297 108850742 931073472 615625689 939414202 402334305 536422779 903871164 371786111 22413485 384855562 92921292 705726766 11559813 933091505 910633295 886850584 228166416 116642934 961892927 318966795 167583111 610767570 479769261 890333947 274260009 492667867 705869060 100307637 113877835 739099297 413743933 75244928 522689120 881885973 14659130 925023424 270825104 771046645 149325886 145754940 8418559 242247177 851481705 19978371 27855033 614631352 906828954 108537801 731274285 721238232 427504595 898857396 184522154 759790208 641707694 311298514 104974426 200093105 411606150 71368613 939192402 825350082 146613540 314397873 559752406 13789021 91937649 830577509 784835666 241263534 976332448 793254224 483510711 680330505 665748946 363882095 294961856 425094252 472419895 26236140 146332483 899924490 777609887 183370988 512231049 419317581 494669501 617205474 619410685 906275650 688574086 411119438 584142083 835187626 725517311 143894489 848976646 817454959 826988349 486328663 58718492 803320797 132099238 394745554 336167653 797848184 758627649 631129508 222942435 83563895 509881999 221791269 983488384 140008238 257678609 348235784 559325818 752348109 965441258 31252854 511140111 654015343 294888644 947798545 341719320 20405954 944209385 190695966 690377264 771197734 677024628 601612107 427034882 809123866 848874013 763202534 459488401 460018013 246848393 682430835 543581907 609246743 756738455 379586643 749254980 14417063 727822426 161097149 619281524 693263683 192350003 130421634 199795378 487238646 930736530 541514697 360160951 874945915 584727014 903054566 498660000 114267994 357183024 778211233 923391859 206057036 393930118 235396611 666075048 640778510 917827445 62173307 102541604 527082251 441759949 851796584 541499314 169582374 12893732 13297189 715362409 57760086 143718822 915157786 544998731 926971703 309188834 757676033 654433969 893915848 660730598 5610320 8183841 17913622 783821552 784092051 76487009 177751669 19488661 595078409 671046530 789832457 657251715 773588134 169431059 99011663 625384717 710930372 121110388 490794800 724227560 836472796 548554886 720462733 604146933 93553616 499950788 913335767 703746001 154384756 659767966 216992950 159995076 520468158 87422923 943816627 157076560 163909932 974084648 29081572 758988340 645131177 671430380 268756406 271235662 840861438 367768068 896620378 404308162 488878455 239931530 128535721 177867603 788486415 701514806 782014535 734556382 53981945 547866653 438302382 208366700 60150970 655295332 220878127 580619127 742718254 17211106 590212038 759144537 991295753 619293609 370649228 488943281 143240340 639405633 760178943 984101778 7173700 509315672 388409939 348568507 749247201 369462011 526436109 537733615 923493168 160966995 124806349 977475112 708833648 563108730 38358164 768984617 70920413 259236290 202120096 666155019 276447395 792332133 425299555 267743147 264142094 795948783 756686428 407382433 287870767 369381722 391484210 147560819 878697393 632410500 496129325 627944594 1872511 875081785 18194560 777882030 36048779 143000908 755357142 744882426 558625990 793715305 366383395 629546402 52951594 568503490 148217772 181915341 360835622 573517327 449658487 624977715 221982461 58861266 32360148 509853227 428242987 276360709 657414045 159456732 908771209 6059721 787401325 763160071 881141505 658112236 393558452 769706636 801113144 1431945 367105413 212255485 795147249 733488807 841801886 700615195 301992296 990019658 882530535 515344270 416053336 184705373 140321984 490552148 96082991 25198483 405374 524325977 154075544 510335771 683782708 915363104 368911843 323700384 531039526 102569700 981812620 924597977 872276335 635442115 926029922 239381747 847697599 573693522 972870554 542015836 126825068 127379201 384551845 9355602 642723470 653121532 46577327 635561806 143673679 142660317 513276640 996595405 519502645 519868535 359447527 55801705 435231638 728359369 379502088 966271163 830929068 213831059 743385492 703205402 701789525 669415413 795103501 402003475 95625286 620490406 944019311 222450354 747869606 181087507 84322307 243109428 834209039 130899633 731187585 830399069 126076301 96980576 826994473 645578946 616849111 38958351 701380650 52080748 767317720 80882737 870868263 598246787 147230148 466770106 153968541 849019672 136185518 949072041 103539499 84327155 422078798 47558809 306777508 22464755 81162667 391099815 265574182 767888057 521999447 996761766 598287126 648075748 93742342 277797950 146171045 563107804 316756301 847551694 467704903 84074020 780950782 191089517 534837158 928180929 657859622 541322050 629716953 646561491 342910442 733256451 730888646 764989239 633331611 37666153 787453994 567010629 428765967 53028175 334898686 803281766 902306293 785702163 303873865 848564986 63500112 450044909 264189141 232772764 297596602 731894043 169363135 78547383 922983560 556716645 859244664 580843181 98038694 341477968 79921024 440949136 927250770 810809669 58454726 413098732 848475821 845908719 980109360 129758140 751453246 167524397 933039905 506275890 953226559 89430121 207357227 869243023 539475029 471546367 102015786 837071630 203440409 123895273 768135364 126423968 680611917 479896379 559783501 631166962 673890698 639704524 72116097 601141467 303030544 130570823 14240198 4022716 828995893 846865910 133780855 580449138 14390306 919337111 86725027 967616865 8767231 146598605 689376239 548242259 618144971 643908376 237830240 821585380 767803648 858481956 800525699 300931916 190894686 212825551 932098878 864785384 705046426 856731326 318443202 8076969 839818500 185199752 12099685 521330745 32065661 145880539 101779882 46455966 917734002 41021261 866589182 926501232 40136217 408481772 327259843 658281188 52390148 417606434 332382919 672710147 276088389 132908617 973642063 466983075 198250520 758257292 184284810 903296945 467504969 502728011 763890266 159839821 687927762 775989950 681170565 719993422 774386840 635466798 618965740 544637193 529004410 338071273 323654777 569140627 746553045 650914619 79938166 651459544 68521052 412321084 324169690 197125793 397746052 150328104 516625219 595996571 761101747 700910028 351809868 81123068 203638038 115700133 240962888 891565800 744206434 774649804 464075573 371109625 262632953 935557664 915746818 791637363 126145289 91917946 213294341 872698333 742832564 293232506 376674228 663869967 705553589 700843917 713512111 103299640 703688373 230137329 551812563 464790119 931047356 756138782 545913186 987201746 724355266 639392425 731283897 321078051 414042228 47875821 692187675 676675181 983433485 460450844 320828895 109578773 552368789 386639587 834793457 147717704 679872092 211467684 664104023 237942032 764827952 377616133 193758023 468516324 460269814 598086937 785822795 243833521 354225718 184252332 231035266 78580983 823644757 962319162 252175385 90203336 10194983 944363060 766878516 846144819 257330255 940223762 955723591 662215396 326863348 643033399 809933099 859251791 854501082 326553473 97193822 471845385 704169606 143468197 940361709 16955771 741555133 578700855 260789291 948297203 762953186 491824557 879394537 586597942 306660070 131569922 676801278 169371404 928449333 296196145 15516222 38295939 88936259 823756164 700511334 415799606 319305914 362960785 127567749 26323347 689514257 77277922 498168732 246200214 220746118 291046792 263155984 814817603 869747646 523945275 763114805 632700831 15769831 495025693 71815125 174946252 626595614 601132754 196834008 407561298 897328898 64866581 445857237 986265156 888622745 146368570 254581114 60445010 509329354 382148862 86768357 51359963 459426783 584937088 297560176 532689253 875983879 560716160 347506855 745731524 84661434 963138011 230948706 952947616 458163703 155280182 127893867 937275669 756412935 177244226 344836966 506258185 242110807 790694202 345039692 130733551 789579124 599620805 43694912 151424829 834286018 130463268 202784791 146229153 715400355 500344967 678918405 591384233 61061126 26425259 189632108 145722559 842079621 273097166 951186526 152759675 428377347 931596744 90035343 184790282 108840970 287388661 691048466 350951776 78082862 36088157 334201678 720178337 488225314 377896589 871603166 175027683 508359857 74387956 321256835 76276563 574732922 175239 667660796 488310399 879116849 709809255 486549309 721196469 982906420 437735834 873956144 411283767 221848930 816507838 448590400 330689899 103896498 139638865 534158026 34495712 28243373 868359703 754674048 368985038 98772643 478793565 544012721 459648851 553181521 865269555 535925414 980430794 717961146 56102561 468741193 597077994 765911815 955290501 170790815 748818235 245542687 897263310 12618353 467391616 713771147 461208752 650597866 670183997 453363968 184755891 704679708 334123692 905631945 311870107 555625082 4404587 790663672 99637802 316569790 196361544 817423708 852495203 29308689 387901205 908597763 498049881 984979199 674509577 305856734 8286365 275844163 403915772 905549674 140978867 871307387 471837172 602187618 374421604 142021168 908067937 559177494 699217227 94707981 317325790 863603686 650333062 174246728 506783709 602487215 490816517 703145252 272427274 343311719 732453940 660328479 104425833 83020173 497824029 778935410 241393258 506110393 907295924 645309029 264176418 48274791 369132767 588529941 502978760 743554370 583067461 411046697 155248215 134801039 505754677 472574004 998404724 8604090 646820731 505188432 611091304 137637248 60850035 883518577 333465318 645820327 543847055 437891151 728840499 41671083 69342912 970233756 400297827 976638835 468059136 516990596 24913625 837191902 105520537 380408737 580746271 688587997 791455433 735994485 823389035 149726461 61084840 674310111 158330550 707905570 32014894 769421853 845542817 92864929 505456781 31524487 738685255 49303836 469415637 320042105 943491270 538758548 142792212 196305449 515397382 610851347 713296044 392827359 300559600 671332932 773236095 881305870 212437280 417207879 469816706 35826315 419450691 530901545 562652777 577781240 91323466 594667670 199719444 936866283 687532598 705176224 968390769 278734204 606996411 290322757 451292660 403004033 829081304 594084871 451825833 196995037 57452569 17638228 589822395 358012168 688971160 215574841 91834389 901408439 485299071 414167446 789751105 904749761 945068990 352403881 335047352 36392456 947071551 534766795 825775090 487120500 92459371 646682210 618371056 551972133 937004966 69663715 954976165 618602621 516264938 259318349 815597657 573717506 276956577 257936404 784246026 965927736 473511244 876080414 867336174 958810315 142764212 509603631 716076427 87833201 862007511 51123779 976742008 661595413 438406925 655033449 1232265 530866295 154232010 619603320 82838428 943753327 541783386 890330944 562355947 58048323 2165645 230469956 484282181 279122221 488406359 268528206 245049956 961917602 997124971 964902481 773244268 139889182 474506111 341837047 80238735 189029974 392960825 909497094 703141738 831367749 417046895 704374002 214750396 571278904 176493673 150105175 367548583 718277059 892952470 929904529 628841733 895118114 12890836 113123913 174240334 501297194 234168470 271806641 315731148 231293441 236709122 88975415 223698974 563731584 283328813 303937708 752761557 676289637 65951154 308419647 360173738 482998048 12793648 427440485 54276951 41803673 577545659 274341885 612597083 323014480 56762766 241438815 218132594 69653601 207079080 244889279 570950795 441247549 516695920 886681942 672540989 753405041 828173708 896239963 169652976 111502521 52694022 922414533 640308509 118645175 83350531 482246 601643222 96144178 280439082 508436525 990464202 857984740 782778409 603061284 33515572 839541174 697016451 251648165 909194775 904095530 496537443 332661921 345343078 13233362 219343862 870400419 619154754 47517569 619156733 788807730 11536441 671850754 563738614 651844950 643012281 647089144 504843547 97171854 595749673 785282629 605608378 438730227 495783720 240903139 41791510 529299291 932960664 591324312 633463807 694671790 495419841 130001250 27333710 693279271 995750963 99193923 563679689 467422069 146711492 35352773 108746150 10764284 707203526 525001115 515125585 202732158 24606610 19969132 299904012 620356282 657768112 905512389 59086508 6068183 998931879 953394370 387883826 931892543 397235033 21347632 479080684 892654874 3865233 506414394 438450496 852132548 605608316 2130184 172070968 604836159 37482956 280817117 468116795 597202833 805818231 983242379 799934991 830424840 855727862 99839002 303297473 366012325 857867742 214900333 372080508 709315973 20811054 759964333 493724867 418046086 633828316 972805550 163217311 637693549 331736295 601667806 342342448 937344611 456314341 514413415 394697121 346313648 795230531 862813915 796032833 453565113 698572646 448484175 136506304 554300507 400839528 292320128 920312832 111223621 507220460 144909691 820539593 380547865 757390375 314264459 798593951 391218690 139586361 814327613 881428590 471322655 268511771 223771037 261183617 724826111 738184451 655880738 923656111 385931333 371211004 719688943 692012797 69783649 20689469 828519100 476600508 421528996 120839228 249429691 532752616 480576039 246855733 353292209 861123904 4246107 520073019 512234206 247981148 659659379 179078170 129409738 130982034 447589940 205697126 392165650 24932403 943881577 900562739 948588513 182329261 124290095 520793807 874342058 46590095 541483275 555377509 523190602 963012270 528733088 625136644 495764885 861825479 871992376 701573445 575465734 876238482 221646464 87699939 124219630 881305842 119294460 106145719 864804227 566884400 311842844 109486229 591816802 108240772 10048967 540405314 143086385 134339061 61199120 17428442 180929156 455198746 425322302 556636109 418211015 806571742 181772753 766492251 668397220 53765128 468065696 96379305 782519962 542228511 36595595 759255943 276050704 155890054 717918013 140854931 722774453 29760856 250341159 314591254 990517980 112906477 707512919 133604364 247245538 621228390 3549157 280691045 76427135 281387810 837327153 347154501 87959551 19099905 113646752 608873122 925381385 434228799 705252426 560417698 976457309 741848020 172189992 252508012 897738074 890108004 245879294 620512526 772385211 496220452 787620132 615419542 609126929 495133050 749023905 708888818 116361440 605089413 989579862 45304926 886477223 826907014 392459427 974436773 698523271 358622530 435826247 476421007 792851328 141078672 889355056 769308636 882926692 61545047 874332999 633181117 804169402 120212293 106209994 429070964 468949096 893830125 44490506 78076024 241479527 646030762 639481193 210357318 103636527 629061054 255662243 990113749 308484420 500638021 817066873 859524042 859260550 252893119 188461400 652111877 246488143 77816455 273936864 129414834 991877853 786215 615112302 648563606 120998507 721322295 77634569 589947602 615152420 974641426 520539978 856631946 473188540 12537522 66989263 576825066 641598576 175167857 419455166 802599347 675805878 236522038 662123388 387582779 341931509 850584787 39694656 588419651 780917593 166147871 570350836 772795445 166934085 185463137 273875402 140448943 906785431 204026322 730396545 374454202 31184100 103452874 83602499 504372639 115990395 3108113 933714056 610105322 30792322 353169221 412704668 706598199 442207610 927344407 94180977 784139118 630445545 986391984 372558768 411363137 5056207 942909603 36674933 24506643 980889091 310550334 164955586 740190874 514576656 895352130 114645075 545760755 851321355 50763926 902649745 967311749 53872038 836363800 429933423 84664359 42049372 842638090 643778909 484256981 622498849 590476238 120912451 252944393 429384573 493471218 516823882 286957131 288897173 553498814 311463774 122302615 716565500 476419359 862493488 83658507 224287840 829654915 629419261 75609194 880418840 384585357 895437294 786807229 73465508 325370716 723987940 115514879 20525158 220283200 452288211 643024006 663275789 573200661 748484750 92660362 66671879 265308631 232133844 208085403 671323797 543597617 330388017 387889296 20016975 45397857 471547802 244304814 875052771 953483414 172430359 607987962 338068770 67867653 247311542 411534277 245754720 971299481 379565507 266279877 44099033 831853717 761820234 707374821 405054378 510304984 652551534 324242608 628129966 884685378 384844362 299453762 280799346 715232378 539859409 300816321 760630234 11407210 397637486 488199356 817406975 570067845 96187317 7992096 637935497 343498859 419526372 883690216 167314691 799091878 2486445 63930075 483461947 764306678 771304896 888516324 127128013 276372781 65275283 755257979 13574510 450119644 907228092 294373856 17868373 447087501 447706528 631014959 311011062 845344013 119214314 128418037 415411857 67917983 136410132 905863705 411416841 408452856 642070273 431247883 60061085 644556717 495177958 543523031 261379746 118999205 284555706 241024111 395371985 202347340 996282089 261462847 652466983 756026532 555836702 522851708 55630384 3543229 153866666 366641446 701403593 125597331 347575834 116815450 193515313 336502317 875195506 604932153 597471524 517265778 36180036 657532609 14338846 383874345 53571991 128234944 502873549 190644049 369259054 898245533 392991388 218057494 12224731 45458371 974084025 568061432 420826430 29714409 424121012 574693095 248872206 125524605 700290425 596448039 94856406 893805738 785466707 822568263 351254242 382938231 192350393 239950629 892987191 206689238 623824973 946559181 334924181 126698521 137203229 704183234 877460406 382710969 922240727 889685136 280685691 748841104 310262920 701512120 778555512 586900283 128721566 27427717 564941239 829011990 476392107 512313996 575334079 114375165 334882259 779104673 497313395 527232651 19055301 242816937 586438240 495396626 41892470 921362421 474611498 31612050 478062006 204588255 414323018 252819085 946789743 695008708 1660188 109569014 396520827 632732051 696469296 525242392 512676119 261410535 206770734 841584577 773724530 634621164 955959741 961123140 413725836 305789488 340872142 285297489 548606424 927310382 633210466 590498893 701189154 107821963 622110943 31767511 164926570 36433960 284586595 111716312 731442668 138763134 73801677 980479846 624011536 770270972 358238590 136687654 31681506 565009323 830788582 657922388 52146838 786748323 471561879 465872674 92537810 812434021 603686514 493660585 739744402 236896979 84159478 293449907 197235293 706270420 325217417 214678214 595220731 609804012 178910877 179179750 601083497 252712553 159659596 225095033 22983525 517898185 214299038 907181382 935423859 45087620 417620121 987570696 684352294 889182000 305959721 629406455 701616020 909646234 123067039 293876773 146543212 59742868 587326679 196294857 618529639 912544095 410973070 213750370 374864458 589883947 392930119 975947955 842596499 405106066 53559339 718096375 923004250 120374728 625277757 710944460 17978699 42897877 698515156 702330992 784596228 4474876 184253798 338728599 766637462 159837189 632605371 765697025 72096408 72448401 961991881 690626047 837508848 225481303 904376416 64889657 667881601 149822886 40837611 362994451 554928952 946913301 81090826 330449553 67288029 558884934 41394013 85266727 454299162 592425520 640114071 238895390 449416747 824367868 577623988 68570560 836721408 62745711 834267585 908817816 135194111 648775817 599443862 825219310 874257119 356336629 890108967 394655071 358675866 783462929 757649522 913604817 730376230 838740347 96570722 650180610 250141632 990481086 735447336 704440793 435422957 228077758 943336182 884839703 52445626 373476522 953410263 741683385 288738584 640194199 650501200 276449046 288970015 102461413 101668356 15743486 311314393 991777322 410398556 669990259 627756602 20564429 436111427 210649183 859304775 532682148 860829792 109446406 375679585 448793480 666403551 811102541 676871237 462256084 548458596 581833214 835732605 354385210 323516599 124471188 994579408 826534150 253436586 136065774 928995563 355104941 151809259 92826307 199398614 414724167 762816565 827155215 435288595 198927992 37804398 147109722 584126491 751150541 109072479 959806076 199944020 775476029 770908616 876815257 237732113 171883563 311164822 925981069 526268772 634681420 902968609 520848179 313731922 156405194 656913953 95243836 364026486 661239563 188070142 563425099 75963729 950886707 243096665 511252324 2331050 133417414 658362045 586457540 884567955 767434523 546263615 937028326 395426904 169688583 666359934 633159016 341572145 977524756 411656436 867840917 464722527 314625044 241205447 778454448 323546589 750635751 873698283 687573074 411875314 61768425 103514524 340355394 12655131 346611189 851607717 14986180 332544954 362486113 453960071 69629260 982436988 223686 6657586 377863891 22428620 673017519 863539258 216517116 503058626 275195693 84358032 967781153 442337089 178079831 746235600 765883677 928715581 472450235 453456751 193107246 534218659 556971274 533462640 399390141 756098814 237586708 266892672 88643768 452589173 720852742 158273027 435026160 573592779 17446964 665406402 448537750 690464483 528945659 665054866 46039460 656657703 601929249 13820612 98994791 780009079 612572564 864878468 561241012 85022798 170851570 606864609 471757808 580339195 140327248 871147948 336438009 230430308 990556971 277598128 683019480 563926064 435871154 970561991 137518843 453318118 635968392 438572944 996298952 17430402 103627809 42338411 674088104 705557058 56159023 625599247 338082488 521247938 342994066 751839851 606270735 513845635 358704460 78028542 94184829 351548059 801692841 283139189 434494718 644766163 560737316 117514197 208692226 849124822 940592539 198727420 154959291 429077282 637300364 151258242 446507683 593444524 46113004 973112139 151517933 102272026 598711385 489600421 476036315 941705450 93956623 82307049 308067436 452661082 12851942 254768616 656725493 667061134 390424157 91220210 164343648 951161472 61250759 373035874 652802645 1843297 424279645 807761935 283436931 61580008 959020176 729944613 507540884 5133180 555573103 659058816 959921557 6800839 1175588 288474224 948506288 95132211 223297624 109090075 547793292 88665918 216375043 57035136 755727051 606799199 148255346 920070699 410477022 62022456 145622924 63279667 63865752 569902568 871041601 199819034 483998928 682578129 929763647 991539811 540227660 337853101 503114978 352665568 344653940 504290566 641139791 145676579 599422776 864437415 254766654 147216067 953103332 471141696 56767555 561346734 77940894 205022900 333933784 340934267 267045355 332073059 404213933 183427458 901975627 127771886 383246492 238490906 662866366 165526490 82547068 55610377 503379590 585662045 408275944 848033529 89952610 901932087 993710108 541891737 618885853 100993113 541624156 424505536 424651160 598391710 985852269 355108405 803414609 172302405 696042671 922976315 504375463 100256604 106403772 258867441 80544841 342166615 349874698 743411206 360209456 432421765 799021582 863589046 870600162 59813877 564138926 813069123 961745963 410365385 354960860 433148167 363874849 896585015 857653702 788526008 347493076 696022323 143634412 3424036 868324727 839677083 926400350 225216541 792450038 885320473 336600334 725511230 80003440 686475031 321438787 440212895 118896796 120460368 156318292 842013309 32790596 720457218 655082431 847052911 983338954 862559642 280201077 347213803 611661008 137854779 135739810 959154083 686393453 131890574 962578118 407234531 824084008 888978467 632451071 469050397 626815292 969051404 194561626 706818731 508042787 516000412 147031625 479455934 488977131 303349917 321469242 374284078 876323486 829068024 221336988 859662439 691627666 354054417 59392593 155805025 344425547 47648755 114959108 30818999 32055680 77537225 438053529 856139687 819032044 923020951 325190083 298363687 744588707 372268060 5182417 252631493 888268471 4730393 732087426 229761953 308080309 906073019 604046030 36920146 735141042 677899370 896582585 279285059 31953786 808491529 435090084 376379332 856140283 402565543 259714682 888195962 332619119 697768210 596852000 4167514 473305512 922042082 302531200 217894218 146826493 307713616 323042062 35094963 312444009 55129487 117373267 473040669 813718857 573935649 509960815 401376251 251835018 259059751 680661309 136305155 67551279 968267744 512684486 776207914 370833286 772399167 516920227 703452405 322683728 113772227 707619918 795989239 888330660 10151118 866399809 35157153 170381085 189441870 922768467 335341445 97087709 40141734 808382114 910806565 466593734 318342928 164699167 718428751 577402678 845360476 854733905 497470308 666144571 219934742 273678221 36977857 844850260 790598448 592946613 20050339 756887026 153082882 816039577 645217685 15750351 534955737 532891189 38647788 724397607 455659656 373989232 674001667 348317741 182371345 437324583 814911474 353230624 602023750 385856576 930633301 299900577 93106832 280619961 966045147 165557925 554298181 855539355 10408184 197412980 301002319 30458522 954300005 454085201 699014450 452034042 322351903 233970187 984925230 360999690 810884145 293101237 734988922 484885811 493935329 917360266 922210393 161363154 123107242 376750494 547219729 53740542 676651070 492842912 186876854 642696217 658400836 741175035 350751923 668809019 791104366 651754242 551783892 597920723 105839442 250798342 49954764 280707696 337284880 887396345 641707386 148169024 33013934 376696307 485571186 526949262 146572924 260297930 688312416 269680165 637048424 88048496 175937059 313699493 580891408 362813912 808912061 91808595 956505298 159663984 760617614 747609664 811418225 164917857 198046738 769774018 415716198 100517853 50481713 753001077 987914197 544705450 753686452 873444482 921401756 239257637 252910096 920491032 499555567 941222511 42687548 136603990 881787358 218624606 302819834 315195117 433954870 111731895 407003712 390460167 123912230 20137677 990586182 787846806 185055533 188632919 410137175 600771731 289150771 313135239 206289159 129581320 857840689 959975611 3025801 631758796 51749599 108452248 552249827 403821517 49674758 594937375 392941858 783978468 666078332 695761692 99173584 100033201 660009938 506177295 343009720 636438519 526314971 333595901 424285324 711370504 374745172 834422498 164658586 663895942 74088 223464096 645993613 857914776 35956058 501535766 489673572 87705657 609988013 894439750 491527173 512179123 341893476 884469031 296157590 7971808 432747074 247847525 108005008 945273363 754024820 303531079 581711881 132856142 637126980 858513556 696742997 11872151 545452405 861401582 528284444 545526492 84865678 26794409 403441268 120821735 528330174 745631191 61043743 138318186 640070940 405087268 650497308 981964416 142072650 799171249 842452575 574819723 47018774 802973934 372609437 653559945 106505013 954321317 786416086 596148344 665351224 335675435 460536846 210803628 49593368 988821289 756330119 134459045 15615697 12287738 107797132 396462222 757918928 21357226 534780408 250506220 426444493 37794067 84986987 568517142 836965316 927439561 995853216 736500441 582929846 368462652 390060385 689434858 175300320 28992822 138099553 840651543 364668256 598636398 903971522 414261624 439974039 512817993 401237020 308106087 525105730 361550503 704568309 135541010 235424081 91865068 238563581 661868573 129659134 323550567 82902067 819140801 103506479 78755282 555641241 686436324 299734286 798217977 228387534 327550957 827210799 366487086 20718852 44395406 965123484 924690373 311173381 257613874 437508365 712410401 565719960 815130447 926477255 270288268 950671456 161901335 362153335 41751388 676286260 344328821 365301954 759188326 163469621 321324784 690459959 571627214 7761107 842710596 369845190 88664992 170261553 49572340 307668430 190980404 93967746 125308265 115670776 257657478 382922138 405695493 970067878 948642097 73342291 749061485 71446717 24013746 910962819 433600051 65765133 439765430 777928871 283583438 51470107 793914844 604908221 741930066 365542057 465185679 437157013 587903598 406367023 607418565 637475938 714035452 650915320 583960035 839343716 619102448 841617512 222265853 24797940 664201742 23424301 98140230 265779578 94871017 974670327 29258748 528471068 892951811 469024178 158916290 29051600 520494284 952831133 486476172 114940701 170889541 951661850 552097714 758793139 210545224 12032630 248785428 924580675 662947950 685261814 763924390 282050397 379395677 838706594 159364688 43597418 862130895 110021269 161893347 957001911 937207947 191152095 337989330 682676109 660176272 496905620 711727708 180670555 302253104 50720231 295611256 325658997 2382080 847708969 84452135 65443656 859741598 185753914 990024330 375205899 871015727 606465072 657256295 102927755 445171665 669137334 146525173 159818911 779158602 160934871 116820822 568882900 352086965 454810151 251559008 12263236 804232122 815803067 45450143 106485226 866523297 341061398 284660574 721421729 41286718 221629060 786865384 753544667 407382973 776889713 128750566 130915051 235871136 638523212 233842805 681042801 307660546 232884329 840861711 939335499 393819200 810198884 508218399