1029
634659043 499129832 263646798 756177727 820393329 696543191 217313811 316719864 398118494 629107905 445919627 358588079 401386817 241509914 203435478 731957183 374792724 379395187 667431351 52234143 207618616 117092692 47247832 921295778 767451622 246496347 72290118 32925391 3834084 3722242 774519119 35693161 171716603 757809972 329610179 176568493 227880442 760499725 987478585 909247118 674706423 302153263 185774640 741499781 430048773 383978472 707380414 251817775 801634227 234960086 552673277 824262624 957537202 53934190 289726132 896555790 108513920 855977298 687037233 323753759 657693877 670972044 693797561 809023565 795484795 875215461 695816591 303393820 572782671 281403341 648751685 40753267 111439726 535966908 363841592 825094331 269242979 246016739 266747636 397130089 590007991 164987931 368886729 298278455 229972113 97891130 913056902 548703137 861409519 992538761 684413528 325730634 965485770 846720316 273406017 929081687 705108310 546118730 975473506 566279660 557979276 785682605 520429538 563807395 711974421 461855261 724130430 903281198 285048781 107698000 544455673 565735809 881873600 418770369 31896662 159023352 741802377 309929653 321619886 517735083 722008244 919022510 21707087 700759135 267148147 675238690 910909556 309039084 225281553 62516034 830267130 877264860 928055616 519665914 914388039 919099797 815083101 230528996 845523921 681013847 905881893 230435217 117809714 565044144 830065778 55619789 138882841 742536192 772611144 940293633 58138339 530720245 167236919 239321417 641732898 369842477 12407145 137613130 161531601 121383637 916713558 594114758 225527254 707863491 170221436 584399901 287409775 984846928 483044901 266894124 443157796 359601761 973932797 291281779 211410502 409942074 873292149 940463882 681869178 377434048 875787951 445872842 510147857 551564670 819453422 979570696 423870706 793899379 812915325 660110406 584130385 50153223 847398973 592995339 74272434 817604093 311990359 814797456 901034229 305735329 892938909 388547579 183729265 323008687 67892600 90645262 193050686 246700626 643377010 210590942 200255647 927339326 917045259 493599272 920816213 181862858 672851853 794861902 363673320 219829662 323752801 285595992 103999854 957379353 594351750 478627252 33261089 476753983 290053635 724325151 207907968 168783540 532000634 838945274 188663017 142549621 639188403 922527120 212076046 890274574 677588229 661650489 825094415 134381622 73127920 135212640 267213369 283195151 22246506 765435643 868392333 142947973 961499536 462707692 666820851 322900111 718501185 338373709 771483117 155620937 644487669 904990904 107855343 787090629 388994568 614658795 75393146 10603813 267355718 568065695 110383379 78815624 242178134 275551098 2331080 396348951 10105586 596531302 491181378 171804134 142598933 220450208 214272178 754072794 112205312 809682104 973442362 598322411 401522401 816204429 595101759 21537544 615352737 552415822 851862443 937334200 477183036 721895135 334605973 743622219 580019841 184026196 392964709 490278500 403776822 143135002 567413283 157556397 491167997 788346408 881220913 88065322 414171459 263860316 627757715 519242839 660868725 537462200 26534594 679543770 935578225 727115350 966629435 351795474 897711135 119647279 987588611 449102800 637384179 556342505 170708326 763424918 698618191 246785083 373802145 456082827 472820989 775008408 717022176 692972844 887004779 669101386 301655696 760027675 723942222 315573570 677897022 446190120 777620219 54902104 885643320 429946005 894657324 446801302 901961736 10928402 47724186 107831946 659947779 634277989 895416182 167576306 644865501 24448027 903657897 170832100 69476801 63478987 386371101 607701572 545931624 175859633 19057204 977129744 296278521 658507222 159757597 139257899 726828533 263330265 556591974 141150644 449898576 262239185 438562524 676072908 365147262 462707896 364643250 441881857 529967168 930528798 276021745 374197434 731526102 131843058 500198565 508136766 121778959 418283995 71234405 238604801 108335809 857114837 750635759 267600892 758333427 962525287 915053727 423790688 513108337 213275775 495182355 814817698 562611009 358978832 197820754 798355171 453452776 646827517 824612665 695259552 857717856 251760213 120017308 702039384 4599874 624755356 414519064 951661897 759302937 691740220 862371853 361680190 566296562 638716557 345922560 236437132 245626114 285097139 737405457 217286257 412322085 56780079 122767244 774930782 980432228 822188784 392955175 170381274 581431874 213601268 497171739 53452027 650003356 491200810 773618469 46571843 458884450 616979452 774917406 894807365 275032903 103931329 95240101 545201445 290922312 775171062 565891845 653909235 774150304 870012298 365881110 183268832 992494845 276138853 743895438 895734307 684691082 648239661 593732277 153760290 727311276 362400890 92827891 73632833 911095563 865783344 720014866 613775062 501138042 438584110 154089443 167276553 664035258 469771520 543435047 261078060 659160224 462467247 374400198 373750565 774628128 20955085 251569047 49532701 671103780 502530331 49321090 376930836 110548818 403985597 974633918 5918214 65422139 237108038 95978142 182557721 480622860 534289412 958750859 946788638 910003369 593212607 692927820 820156086 178544107 611704022 420454280 981605643 71762276 905369076 601529844 157016945 670706226 56458393 848519385 916287925 342018237 15901889 177206499 173641232 853956413 796764554 749088193 99201836 784978900 92521688 354571173 528749590 198402333 327830501 459570674 134060482 420677902 87496751 803684737 692612436 577793397 407191670 987069748 259974603 421036379 143431875 976768433 367480738 699002151 206540165 839079437 604590638 727280603 445113200 594904885 287722936 49356904 649567047 59536500 77453105 139441914 538727612 151737889 272152713 391444074 441033434 512250464 261111758 767000662 858665372 287869778 807602537 568676520 44981509 168233401 880002355 50244034 918414779 753775407 526115936 878988289 219614147 788295134 87212725 161357221 764172668 897018976 793540438 945656166 545164925 186938836 48010496 707624612 303810828 779952855 602525511 669849038 857630473 137691559 608304651 662426174 734427045 674282922 269147851 482357810 780969101 697754972 842826474 111639683 328824212 819992173 537702168 119567927 829392410 623215499 750248951 733153978 945333651 54849568 956301760 554351633 594006828 3680117 224343308 664311255 390883452 846899153 108991066 309757240 828446899 202956053 433790444 371025280 271762413 223049975 60635920 52216518 222901294 670921521 695026101 81890251 335243376 105442650 269716878 804222153 360466511 422395175 254514486 58021096 766056947 888831257 219683938 983900935 902412527 8722589 770381724 42821284 453900251 38848134 411474265 198865082 589163514 222930274 167478877 185582593 583391230 30421313 21299560 444145557 105705288 549135934 916549468 929551954 371724939 712102895 22444269 122924687 421587242 753173466 144919742 527257333 822284600 193392153 4111107 212930088 205393381 849456252 54112661 649484672 610725276 975004529 156419562 505651353 964770439 325012612 223864942 546952024 218205818 177381462 910579102 654248769 447251265 717906749 206468863 526886598 703891422 883560444 265625355 505280276 180224400 242747284 760313492 261095101 45040179 185267683 485238712 173397328 272357432 542991978 129363575 567238352 308303872 256033411 107915638 898267421 281825344 552504474 583713981 422718140 452542431 238450072 679425214 275434452 362612695 828932186 921761479 778938065 295303622 42043562 115060185 397813956 718960009 140521211 94793459 44182188 948962486 287774871 402962448 592819797 538740291 604297423 579905401 710926359 84988484 689331604 445339026 890497207 755511982 331619667 856867080 631875430 795147385 850572166 625879225 757686918 733476033 392983664 258412669 443003757 775692114 323061321 85533814 280711823 236942940 242202554 324644448 199947689 163510218 271229665 588210403 599920873 855396979 602130476 270147231 579229223 34371037 318754209 983777029 319461998 762394614 948779912 132034330 246585334 214016066 428624221 991325973 437293620 830155339 395543304 273355722 951202286 962062551 240103811 16588144 545327379 888595245 289251995 845217147 146482569 678826814 407655927 414683089 445344944 619296356 498955363 725986814 136203601 384009494 62851901 123144825 903013484 682768929 761594610 145462556 86032475 952244479 3795196 85219436 622891802 839162811 90726789 88751300 863950077 72996268 522291051 187798456 809111684 968044736 864106796 328355317 485499153 951760156 819889836 17949936 612707192 811721361 261273763 217806814 777039281 269123056 983937964 222358835 215203708 100948092 4573154 328651791 502784092 171690453 366514853 968553314 900072629 743229010 430341046 289079508 20451173 436461911 250330137 565593496 245838481 466884828 750604382 442515732 502481347 791597561 524987917 599735473 647059752 743190309 49402723 587408452 925959917 628611998 755680733 534648995 726171833 920418674 9138583 648732428 824967349 204215271 217812273 158643370 26621953 54653855 446513987 344593040 12107889 714483547 267960316 62556250 473204867 955927021 407681947 718468554 671564765 543553570 312714832 172096097 113151442 915277129 13870463 254968298 711286984 548823330 573420642 678091948 275872159 3369787 124002299 156749799 283737129 537503524 100905463 405955337 34144673 784692304 262818689 316244220 604695801 419972461 861186404 660958287 276015692 306447687 316923562 376029605 394645423 678296074 891599353 908033224 318361788 76517917 712750517 716479558 523778473 57332473 484701973 10424691 607735392 48440506 692158638 530899247 408115387 7316027 778743557 46909561 347753599 710920992 95800469 603023845 291132457 892682091 814898323 675111939 160072540 923496240 153000381 494927254 120698925 93166747 79560518 145023584 706523421 605652182 627243337 273000412 795638407 637780979 461645566 328584591 411478084 946622005 937386212 678940254 242820435 572433277 578435898 949472152 645333988 108180816 195628278 377197646 762806201 184762492 26226219 193682644 471066996 732142747 20149975 988376793 342198173 34714061 303054612 838017451 603564265 179192001 860622605 309013960 706801805 239077128 973086917 
619861428 386344903 258440720 442308802 35228405 359336647 170940260 260315648 641495398 628727538 455104721 534902592 180065099 817915791 91859790 67525395 469958263 240631729 336071611 826900267 925569216 942008832 605925421 468391176 71760228 759268433 168589785 476973117 948582500 705016904 406440330 36958253 890224805 389519463 815977602 76957127 74222361 431377531 25630993 116685019 489403803 310429468 370093392 838583730 274256732 682821979 92390241 461406240 81258294 599653174 259645218 68691072 797772701 754187525 876552108 738393183 22229318 431356503 134181961 811693825 120830564 176118890 281364228 240896122 582204602 191760167 838012480 702006636 168583180 713840653 14491248 499385912 487015764 587154782 455871575 15248899 641019207 721725368 874574732 349821057 781905824 599280927 6630326 976220840 297568607 592829204 377654343 314813011 677097095 208039836 264780366 692015042 675664396 606598915 475055306 835340835 236061750 215139052 42292925 207507449 759640046 595543787 614933577 296066487 669466533 670803237 802545698 241790541 192393773 655035683 195468472 149167862 367801371 612915211 291633138 524128625 500867490 512074969 64658257 757080011 436359784 270152981 258110121 130282621 562665086 701729239 843751166 74266898 339838507 512820156 928229575 855601908 239163746 990744005 679931214 516999878 34034780 69394030 146054764 136806127 119321918 815518380 794085018 846616252 886974784 996479271 623151072 871416372 408118143 794144168 336580428 836079086 970118109 718546714 184068263 615119045 676235195 653654699 3330874 846217810 279597835 172793034 303006735 693144427 364159634 120034643 795593654 707247488 400285475 662617314 35468138 11340860 453520183 133740023 11266445 401751331 50755182 88470011 618728498 151699336 981150453 956247982 971853815 245439479 852983050 89308006 518926746 348868601 544002860 811484717 923867645 242342335 273652672 492929233 184746677 746151516 278385025 17872655 800276437 413929631 960069661 802282495 757869384 4640618 95784652 883609190 45733853 467617105 964057225 501506207 41014152 875153292 76764071 512870864 166033554 606405218 482968019 903427476 506562855 4362616 702023452 870993026 386807833 732430895 133971340 62998322 437227545 704576208 238601287 503796396 611136363 520861501 505528797 253658985 767848211 284059312 880889966 152703747 128903959 830649747 909146630 647068619 819745735 583494355 892208668 377196153 479842285 319253493 770197551 711861151 359507972 460842790 776205994 448213187 112108925 215060195 76525018 118035554 812099775 54863504 61457423 357584797 575393721 464908863 21094803 990612389 629163312 172760855 495063762 486142598 788004665 893355585 108901731 588909331 907236662 145204405 420054274 29449746 724035352 691859196 959532624 763938804 273157366 902653083 281613425 153788753 298837513 41483934 162347798 731338549 65282649 282198226 539947748 611990124 203863969 477520314 490579396 523203684 660362495 267354817 484264924 797136677 36191722 144579203 242893606 542275183 727954078 630151239 293537983 208060869 736803823 335489912 971887909 593317476 306177067 643626995 49130943 962141090 796565295 972635900 336825199 237650580 818159550 159250886 294138996 198449355 409864991 219393982 779025215 23032123 359045951 249955747 732711657 166531726 307611359 255436810 970734739 539059904 564696910 690150119 848706576 687916556 680834460 388911274 818123992 513619505 562804690 828730908 626459464 103760668 742076051 286187564 939564112 172736892 41634271 354596483 805310119 534645756 494492912 611024677 797334280 24577920 124761513 394964065 376019299 765014402 580504723 221918953 345381243 176665978 478229207 868462293 674244555 919870423 218169263 283088594 342342185 64117764 128711316 96664101 872854024 393057278 980517325 114042170 833272712 331320476 265615852 694097249 107335942 291152900 530710397 414793091 902011532 485130415 842366027 378545091 861985633 250190393 783142335 367738292 223655143 623914485 764430405 672477878 872478138 834697735 322236257 139458069 813890790 962024778 685283078 861093179 707916095 181763962 150336149 995033234 429817227 173396897 671077016 343360920 463492187 618553052 882634180 682386623 34260541 916235856 759861149 699369997 690167824 450435716 286301665 931641639 875079231 209675945 444913656 718649479 698028719 922866821 604503818 298706090 374123114 424859152 543975834 504874196 417724796 862511559 182561359 74487111 218646956 221026754 920491942 684909515 587839915 424553712 391893524 510702620 104678980 354028413 500114033 689000885 85403540 111566824 209312234 272270257 577722269 392953741 922933700 761270743 289522075 371652328 742859848 494147484 929684117 140485583 566330847 36621175 193191939 930683080 255471821 719283196 489766897 548162759 566604984 176082267 282907949 83681525 818077907 835432620 357318449 831670121 379076613 250380338 889750269 682860653 8030771 206489879 84759081 835552089 764256714 618693634 781943553 855035661 310077071 529834359 109554688 765375060 231738453 612254817 629943800 274568807 436407430 447947643 941732840 282194120 847094511 231160823 786145692 445828908 768544864 820976374 340796607 21230161 786747172 652688696 43420347 237745125 57610382 21760683 116471079 312525678 291332602 474250254 674138337 762765689 863730237 132249911 429330192 347807279 852726256 192004560 915228474 271227596 460738965 114278940 582491576 843780980 211719531 254545936 436830435 138344548 402890386 930803890 515368307 684281625 797867614 282236029 180020561 906207635 931499 903285970 648280206 588821618 98962550 555038445 104953527 227482237 890842475 107272025 913697889 193203460 133670667 743732239 375938077 245191199 671509560 610440901 666600881 937547485 618088830 977961098 241053740 551845700 586280514 981479767 365078224 135923373 937161719 762362811 296328271 205117864 283276192 512125615 164267360 971331340 640605418 961617549 592375351 152535736 830331676 839003421 163705047 746176040 107890757 835219851 977250411 716941969 216730295 177973687 353432208 824438881 184819487 836191327 323047601 914294216 27735644 477897132 631370458 896706561 86362320 947472868 618011057 934458754 19380431 19024203 314657668 421901097 687169694 207201737 388436482 213528105 666196598 68494676 894820442 28967394 578914687 473992977 672799382 697077837 243957551 487249327 189816300 429550535 645648459 731153139 713521770 66862313 905875719 928319102 99136536 34330499 399836416 344933172 52358691 561739374 826966145 159080337 529754351 192502770 531639685 39839016 644281900 363286204 68640073 72768086 654976467 976077833 413733371 226965134 657160585 251380774 409235211 153180518 277684029 150970505 829795343 954136031 774487606 513588595 8703779 900416124 943296311 155459212 451887877 80912963 466168986 739103973 680143487 358515535 50081603 881053178 681280944 274732801 634246357 59385318 606839408 110452551 716550473 895387835 658055227 473503795 663001821 567735452 788161189 425347977 358213454 243692025 605298859 627592443 695498545 745101537 484873460 627043946 178276490 892623819 84671453 141949419 691667668 335158796 398029036 120757078 562571184 405424834 570877437 481928952 221414433 712228685 849973057 803687096 348647878 219125599 196039499 903458114 553145345 657180949 510848571 893358492 37699530 262440388 238769682 39561342 744958126 924766429 823940704 413617863 665920600 167397943 600548702 145123097 722958119 616969060 46729582 226432409 68579265 197121135 975729334 272795573 18441598 658830068 195819913 463373376 757464524 342820598 722812661 696789739 781503474 115997951 672088615 723448182 104868930 266724940 947603172 558616104 444556440 253006340 277951871 275156836 673114917 564982116 666853955 829951376 406956145 793585351 292578587 207445745 42289117 609434958 252847103 798866223 505622847 224251715 726796860 134754325 59916352 76199715 123592122 87355237 792955577 196257064 862778776 359412121 915844844 790007181 681604050 702048098 397684960 431312454 412266254 347971444 408271310 957458962 954784577 119136719 934534949 793668581 797146908 747210809 892784594 649673191 485523012 797161396 193219248 355302432 680478153 362290662 997839611 50504486 376921542 96266192 155150001 314328120 314110162 547806067 245966774 299616398 587005468 898448537 185083872 688771571 815678367 643742792 813748359 981489887 886585945 460364256 598637969 107087374 705976121 257259758 883471674 546158938 56314957 996205276 202082635 420783748 664833102 213289569 120480617 684456795 861335695 663629569 239340667 63865499 446212556 480228122 990776300 961032388 648045046 997238828 807015034 114003091 548912621 861864086 183602567 910855210 248499151 755940061 933619401 973413558 871668432 311361724 432089523 92823042 206141156 604765291 375149530 30163003 202277279 771710898 655145290 670474648 215516594 389546028 127463373 854770412 904520536 512714135 938665594 766664402 459507644 102064917 8505965 380259000 172329240 385174241 542961303 139441598 513473337 261813823 591638491 294433799 701626442 455107885 294134484 325234430 987110214 508814585 927158895 168605728 174916602 71493984 827986712 878007268 184180212 295883965 258987413 151174105 235960979 3792564 700268067 854110250 35559301 354840307 893408276 341529627 159198727 128637255 777416742 753600092 331699893 329677241 397848960 946043670 956477671 943596936 464117517 923912636 894952459 647122366 467540752 803608639 588914855 57172728 510482720 51475595 382690940 675499603 575640953 397938688 144097101 42872368 319685652 988895934 743278325 444549196 545345074 407291740 267389971 37260481 884252664 319802858 244365101 139152579 481139829 921993878 663803535 123139826 800516885 690819070 463880901 282866318 156553178 654462129 134947335 621043163 925832249 747479774 36222658 986229557 735301652 591363454 926082437 643187962 657771817 317481773 754632794 796083722 763883879 984613287 438366258 81784812 359656512 551344806 662383686 575883508 341623489 75550054 252647441 236270354 326838328 153897069 716010586 568661871 534565404 494529095 335663204 767284560 785953841 844866058 179044107 435572045 851705819 66285679 993447595 635277972 225365058 471972660 189772857 322894687 107412085