1000
196159556 656231376 985320680 626270016 963341614 879719504 62791440 217373672 530161280 591328964 430110520 606455616 244470912 1050885888 684408480 723721536 889546875 934597654 719847084 376577608
1008771488 731259358 1010756352 740697856 58849239 961687552 164350882 776446080 355470644 100238340 453202048 283753280 890296364 753190400 479611136 475949600 582506584 850050164 189741046 778999240
368333378 327968000 962086584 692205312 810185800 940538966 141534956 249794944 250290064 814058464 367876916 462024392 618465616 958019460 925345696 637809536 185462558 131669960 580999184 922827389
628440032 409912496 51220488 295480747 910901248 699600242 223959680 914607984 568611268 44086912 1069658556 507970178 946812672 588865120 714263936 172096628 473241600 246657872 120125928 359255552
373502232 957711104 687311872 662018048 9390456 18748632 969704038 858199008 237203536 621698336 445362432 1017202988 429876036 647220256 943309312 326640384 944387328 136138860 123105968 699354764
541986352 969825948 616491008 963165544 924582160 978782288 49610936 370737424 829977706 1041074416 395237414 771595304 713983800 890787584 125970208 1022004352 1008224340 122481702 451222016 819666656
200931784 1013239640 597271740 215034714 589978414 61986288 36687672 428943000 244153328 620526840 244774272 676689520 776903344 956211936 7773344 316764855 644099200 933876016 147981176 714813824
372656654 900379328 297293312 23500352 709878898 844832523 44827248 954772370 1067667952 338573216 401314282 829609216 649401520 334115038 340085456 501274084 579188768 265680482 777725668 277977632
519821533 213855168 337407280 691286452 562607896 102277764 520996424 608083168 292803856 1068813776 837078570 1050698668 1035780980 121219072 224033896 404793352 102690632 696620048 179794512 214019608
419363618 839185728 875534128 301275808 439379108 513015488 490529948 129181696 289821248 985692107 270042962 614505536 723809228 523103908 615613320 521476376 96608384 185218470 652653312 643116032
417155484 589096136 120634504 916783136 711736544 97441613 1028694336 793440300 196835806 296796488 354715008 209737536 549722260 968999664 30351392 493559976 376658902 784626122 636552168 329569632
900196488 236361586 959654862 164314920 91700976 791841408 935114288 109270336 928695377 574748560 490670400 881124776 997552752 875045764 318097536 625121910 58387280 538818560 185075616 129171776
711427152 140379712 191688928 278931160 592789120 440229688 429952736 705753920 407335992 1071011456 835868304 535172816 946254880 839179784 80303979 168624266 484922508 351647929 697578544 306670128
137440384 29361621 207210672 180767720 615932262 800602588 857857068 162506776 883584288 796255320 781587892 56870784 570567804 838252318 266780288 425501160 942047864 321537320 760933248 485010816
105097188 681127196 268942556 856215106 281860360 183651256 938544552 366079014 423838672 880010920 549980432 797416648 107520640 934497840 747091786 991667098 429368512 263398764 151039390 605684074
3980160 954689532 74407448 916334268 918758392 984313904 704817966 714567040 423670736 790540716 960710272 959514496 1070993004 41660552 645908926 791296624 992891040 145128674 292572160 3496480
197034156 742100544 846635008 210036864 307770880 681595776 1042907840 503272204 105667568 727241632 217316208 1030838560 129792272 809088108 984344768 192924640 708761486 471286928 670863532 323804327
426338464 513107230 1014522880 959738544 751664580 72077888 408351168 360008304 218080928 967691004 406112514 306091440 931061760 472708736 999250842 486197412 567510336 757601792 472314324 838170800
572454292 349141520 131969504 672341776 108958060 324628976 898027336 4265329 723140608 518752416 714623600 611668128 57794978 241908768 700643492 325720896 274804224 974579636 364881009 437652689
386890752 716615940 994504900 24378874 832481992 427140187 519899068 183934064 702948672 463402912 580056256 708846392 983457678 885318752 184667821 533376616 631848854 771877504 524345712 833755804
142382318 900561765 210106544 40092930 247702096 481600608 675134400 316593136 837815712 929460364 435651424 855632464 809585744 240639616 546476619 605398912 813636576 452341104 735020544 260490044
348877142 1008302192 1018968012 437533312 135517184 4901962 128607832 612492648 986497936 1064969750 476766954 555995912 636599296 80928200 1042675200 655413888 729293528 24796606 666504256 1014419392
433179904 541424154 1000386912 226498400 844665232 255808504 857173624 1071645664 433048800 1030580816 279966244 961462510 1016163071 1058918800 55843711 90855808 295843096 314571564 217683360 346625156
111668224 825914880 39208064 208629120 637143432 827836062 771034360 816204676 270706728 561084736 834950144 467818080 73885120 961333280 1043621696 219317920 1071419072 544120192 818449216 977333824
204283347 331520224 238307632 83046448 491639200 952413685 121469044 944818624 652440608 373832564 843018368 233030888 439884260 48676560 833602892 114009602 740100464 1042204032 512748260 2410880
91924288 394509624 840183728 893727800 603922110 248703472 107158936 713828608 699484576 321152720 76727736 669133164 715227808 878250504 122285574 764112404 782087980 575776768 208079384 799361446
107083296 824795347 103578696 973320833 643138670 192890520 598015130 706464520 327504051 430551208 679201952 460153348 1006529048 385558184 473350016 921747474 260194480 18628120 168383160 910593808
737784008 263113856 792417652 208241980 566304512 169574544 417939067 108973568 239378256 896863582 307071040 50689952 10969284 1062399504 578656408 1024890008 884832256 321037824 970477824 510749676
845832216 785174528 118948838 670964176 627779840 494235648 128298648 151469648 303374288 17322752 58183284 512685802 849558176 818950312 865626208 370792942 805771182 1044928376 590526289 608411920
677384008 433523484 56912328 213931704 1039753056 17038938 104404992 438397392 758593184 1060886402 109546202 61071184 809974279 334533050 827715032 552732920 368944972 40214904 648082252 583024427
465755424 548887530 349658505 200114339 744466063 352121456 51887232 652005379 954635525 95973064 443873336 278008900 236670308 96802162 245974456 766527664 308114348 93181808 14136016 386092452
510726872 76019656 447904512 799018616 631206016 112707840 185219596 1052301440 86397712 989352040 683542730 1047320240 429802112 712387712 800076960 798939744 545960916 330815192 109368156 619198308
533777680 830974397 118234026 34100352 301845995 144695418 964196304 890910546 173404928 836452912 671010390 978009216 247876092 909814016 728031180 820341136 369801062 398278336 590416212 581254768
657807712 1058194918 777236224 801778944 1044799488 889544160 409549710 509588032 337033356 434134784 432487008 986470912 606585856 124131216 948601752 47985120 507474814 119310336 733086454 378150624
760829084 320370016 442073302 587014936 445969012 642922842 173003816 860228628 650163608 737150440 691663472 498245696 816555520 456760222 1054176752 648509920 447986116 244145364 1044048850 196962304
917972992 165741176 656562112 22935184 656798263 278995008 332549708 1028651564 160289760 874506469 950432534 22357664 16524933 907205760 684588584 560124796 307435536 57889516 717442040 1059071136
623809544 746579060 721547104 224767934 656623392 869964190 204780288 342051488 96104248 960480496 1005545376 813021680 21956177 1068962796 754659072 451857552 497404208 579827712 495859328 377048036
661337944 340848400 1004306196 761044052 207165392 118237352 813207168 751491584 930245788 462077632 37290811 1005474716 512462452 920160348 13607072 363532600 226278456 1010640768 123272282 330931152
640420758 803346388 253111954 1000607728 903866104 813857964 346453632 506443008 540629504 419158631 942728090 396573096 614868080 530179584 746928420 801961784 61063980 302690496 127162036 739538096
267405714 995774528 260777408 556443958 348715656 64734720 589558528 126701976 313717377 962694688 716161664 802423876 254227146 442490012 281826840 83792168 730315460 518978418 542753412 663783324
1040837944 1061905615 971669908 1036077804 781485376 560203712 892421536 331713040 776775080 599467700 1008100300 16800000 836801792 1022715376 530649408 524431220 480972720 1014490976 155331438 12298384
635774208 539830792 620196570 881902164 306606269 70800384 959163392 904142448 612458240 781281744 1024997088 514364656 345144342 811880420 492257680 413528400 213668032 922307600 383974191 595585003
767571776 326578528 534295424 102977440 1015995168 5478688 392729120 67827008 157682784 637680348 642030528 291172054 553590834 160542518 722457540 69609968 31467392 18852242 176792248 526347233
800753296 410891216 670434944 529316480 441481258 765378274 580075744 233892736 702543304 296229888 299298452 908001360 1031023008 291912192 346653132 884980288 268405012 883055232 285092992 235018920
736567200 1002470480 182973696 782017480 778424770 54624464 267158528 437854806 117007736 462360264 624502144 819038800 688508640 86001884 252743538 695008013 411862912 388040016 291680256 549517428
174674596 539190016 520333184 885758720 188603232 440212352 703300096 685995460 870778880 871665412 1043452464 309149596 237538340 928716544 262219328 754807669 471203584 614637764 104746976 981707110
1036515344 862750288 262016112 933769106 980796272 698576312 1042869936 38927088 445942976 113140624 132145646 654619740 447439968 1021312277 579296832 612350660 775486060 1024293536 242884224 349179424
135012096 890381056 893084480 1058406976 33909632 774481648 347664960 462308770 212714496 823132672 490584020 477895599 683711616 678591582 509669580 969079884 132254460 274484048 556394732 484503136
637484274 866195392 150313472 197845972 541234258 850934592 1018860288 720585504 639753920 1048063872 981343136 991307264 829711808 898746128 537913088 326390288 842392912 665932128 560442760 151079572
293994048 242601064 715943317 900116452 833686320 234293504 5106374 332269408 870728288 48556784 476556184 520814496 375104447 298141812 270759306 1062266112 927395696 172902084 170941254 107892634