1000
953380832 825548512 515420672 490568752 368171985 654687052 407816760 274646063 1021045888 1034987160 16699456 873578912 997625088 524170688 894388456 736788480 259500392 894163952 194523815 585288374
804259264 417777424 907227532 1025416936 41694832 245149696 609798256 622351232 97458690 590854048 15026148 108547364 1042183144 655830314 563189664 1025999680 173662682 859277040 939479248 4907264
386701328 535597980 620385952 149132010 605113264 992510308 614230514 1049972624 405442560 378051296 297387960 270833164 242555200 58707798 869160832 160234938 628973568 12839062 198823104 884542078
763115680 549745736 1027098208 748473452 671643540 926635040 96169418 776538752 421895904 695592384 799453664 267559162 354242176 242505760 401153728 632944554 625474560 489869576 460945166 385364928
240153052 342949120 932777888 980228224 114354728 15747408 996874176 700419815 671044976 203100472 1032831456 325636248 120150516 493034091 746848177 595799780 650667952 588160720 46039640 811852196
188801432 775951022 44927882 446993888 1007888659 853310428 484330432 687458542 388014080 642357577 478210164 1055677328 715496528 517005522 1052500992 714696704 77939488 798974400 316916962 93521880
164670656 760701654 102285448 980012649 854529714 361998300 716308608 4306760 203579528 461429200 775073404 171112992 149523616 1024208066 379416320 940318878 161974328 135776134 501731328 234915648
805931748 754112880 437392080 314561152 235141523 649903596 331832634 386383872 498679423 584661168 1042306683 796983424 307656992 468051072 38889430 424090344 284371216 295792896 388554064 930517910
1064928256 759435488 974211380 673025060 680217416 278532672 67336348 101449192 522540656 583699940 31399760 609264896 997618576 1042354377 970411858 324359570 876997984 157743264 644640836 647451128
448324408 380763264 817004432 775786016 141872304 725704704 898516096 101845202 258759872 1046155792 84401880 826175016 427648882 914306816 280240576 989187584 43147232 802932480 613286108 1053364352
147228736 897785408 941330526 458846720 365452280 773546016 534002304 458156680 174596480 31254752 1001882132 621920384 1058922176 762470916 747874240 48907736 446873946 404770816 119302912 938393208
317677024 244060000 220137520 177525164 244561696 914275828 48733568 928013392 366642140 296600948 116931568 424434544 117836936 1048665552 932029408 1073668096 30941088 223821296 104284624 73350650
811104942 936081074 1026736234 470591776 700278968 1066628036 523755378 615328128 592431883 197315984 944808951 704175976 827979116 608074896 359574784 581985656 539940703 307197568 918361600 363551656
285135088 705107328 986088760 781900920 137387264 990568128 1037758600 2939648 927806896 106425664 328800080 980583250 1017666350 996993184 149269360 1019505032 850876224 530775541 630363248 510823827
571978624 93412032 534470252 45694536 56051392 162156352 70545408 799419896 815765959 560101324 548487136 462913436 286316800 125150176 663878400 380015280 971641661 55006876 518251072 27630472
96922624 61441352 574670592 1052758080 720774808 1006415408 833854752 537805486 330430080 457787584 324671136 936629936 747012864 386012800 848066104 960056672 193960432 43635488 1002947392 255312672
203418715 374938624 993091904 294991968 533874602 926790278 984502720 126750296 821202788 136403606 537861016 697583034 235218368 618718136 798799720 505315456 433837360 309730432 335670192 950831883
187922692 604491068 264876656 732410320 29897208 335965879 500476584 661848320 306065652 543764320 121437360 343653228 105593356 415985146 78119008 240782428 1014929876 264717824 877269560 267122179
1064963976 424007155 835606344 922214694 601500860 439219232 790253824 41297536 554455080 245585180 761909448 435913088 1008781312 658124868 927333440 998121824 973037744 438566912 918716928 346296952
218090552 937114056 362540124 645767486 655059432 8402512 122687207 601004696 888112240 334532592 970957630 75907336 969983144 575622048 488578072 437105048 578682592 61164768 454431266 1050494103
339820136 291211320 595716832 671813120 385687792 1056772452 896748616 145224576 694936232 176682042 573991424 298174336 874898560 1033258496 1056824729 601179136 733062213 988135760 255750470 800239312
660187072 201935426 70003088 280520966 381954528 747590656 795907488 72793328 208585856 1066729472 310420384 991794864 224159744 410348224 287790018 845511783 732158080 791244056 918975320 829053696
428239520 437530344 594788442 327040992 423646032 298421296 199861200 722605334 1027841794 422945152 34032456 698674032 170328212 1069378040 632212249 964154104 904205808 599951840 656679584 892808448
623060072 1066201568 528110088 402376692 476300576 611698288 922886464 1061386994 851052224 1048600832 521447078 317892660 600891906 163103632 598143769 437951872 925481042 1053036816 844503392 711936992
247762577 456305810 405458432 75739760 860031312 752545541 228130128 1062407029 48232896 400169472 1043013296 49168776 810703896 179554176 901399040 373573864 888841022 473536590 362596248 994532864
5678692 911950478 186880232 514425056 559315738 838803112 454710272 302916464 308664976 263422308 440691176 340801604 107713310 474200048 314795856 899129944 81094614 496794154 256491072 415524504
670656036 976415248 1049740548 66645664 335395776 627460032 932751504 970930720 643085398 115665484 1061908224 323906240 727256064 527241392 373334040 485937984 846924960 318754680 320851436 1000481712
769764236 359286656 672354680 34893971 447607960 745079320 225414744 346693296 125815733 563347456 91003340 201221352 351822208 640524288 419936320 780726064 70364257 842104256 956783200 83987535
722137248 885388288 1018748160 428221524 488076700 590210752 1021497570 617262986 723709424 35348856 974635652 108820316 79357072 983732224 627327576 35464279 423139356 757871961 168606368 1016381104
430034816 669329408 644245708 921540576 593306748 1046654144 1044925529 862072444 902273760 1063340168 743247856 852774976 509147708 320284416 518796792 314557194 465601221 754912608 637164024 509777856
484222720 736860464 200975008 567097568 94510208 605512138 57558656 378884096 715476380 171737300 453664110 10656768 491078128 237272032 288038912 603966464 894730866 410506772 1005251264 940403520
866956510 143888068 995662768 399372224 538731045 665557675 470330320 531604416 711985582 363978608 621744238 403008288 303393824 903945464 556511288 747353952 815716243 335208836 825716268 296204196
918247854 982438384 186946360 652963840 425684524 8126798 636813276 2686360 41784074 269192024 137542762 144918972 870666308 961918448 207842208 1013209184 955576704 380664312 912862360 756216768
38455784 812055488 859545816 289878016 717543022 827269300 979461120 88985760 443193344 424776128 818687206 901600328 851661768 1071459728 993070320 58091712 300597952 623632800 113904192 935162914
330047488 175923346 81592196 529794416 127809375 399807024 856765384 106228684 962634032 97949044 56106952 326709806 1040785260 461287356 6958464 541729728 469842165 242448372 158120044 163681368
1068088128 26810748 832443692 71941904 273785950 831946326 802261512 729898832 910158286 551476965 1073652492 918062448 107956164 773569040 999836804 828927696 1051217968 786380800 719620576 66957508
347410432 439088868 1049375392 736240132 51515336 625255766 81403380 659932284 587658078 611074248 541177164 662456786 1027693096 195145050 190660930 658800920 502904800 29753846 183833832 560634864
807144192 40864768 19439520 81798114 507920832 261246368 348373480 349671092 235896024 447268362 659731768 1042447440 107731008 798796004 393989516 264107608 680745920 265023136 560704256 359591973
518456474 229381268 52937552 963895904 652912553 228820768 349790926 575394840 788080792 690048768 154947600 298866976 591395904 888724224 516373644 622103408 10439048 729568491 437339644 903827456
1004340640 794095856 960584844 717627830 507010992 943359904 490884293 1007136200 652486004 60476768 594053520 338507119 623611082 184434176 1043654736 498171500 769096464 676981848 820850688 151605696
163833784 31160276 15296512 963180032 626410252 816069212 523659540 52431010 969571968 358036572 1046817088 1058583648 25373884 554496512 81997452 272898272 208454288 217723702 93698098 841554908
168891568 383425708 36019227 449848224 984484376 50699480 31468832 306657372 1037504768 965659628 583551528 644348160 1026208179 299054863 329712464 459399448 295540128 41178388 246796188 17166320
129456384 733103912 306596868 748798646 220420464 485208064 312086796 64529296 509593136 17252880 248307903 538435480 221529088 101392400 13448401 465058304 208247168 688207392 99257268 490180208
495433696 895767792 169187304 514968064 694796490 38485870 485382070 474529052 1053641184 856835264 1057143920 133335552 237876198 846865712 845387328 197180112 311860648 893399144 877903644 135651184
848931120 609067036 944712874 136574096 264172004 1066870272 34023036 178578936 72589312 408238368 740969330 793056972 595475324 375229440 585536768 309625504 439838023 264961526 919125248 289001088
877565136 178827712 267957628 4360684 857994624 945489152 410101832 493266902 1021294592 777929656 625895456 247724672 1045718117 383945848 938203264 348078304 1067086128 899220976 239233088 286007468
621343744 168550972 793721264 414131462 762497280 660599507 42717504 424383284 702994640 346653056 922204146 361448764 680531328 355180544 417485184 113472032 936274300 86147144 825671884 45512032
770911256 927185664 168763484 928973248 168073656 37596304 993514108 248024148 21048352 467246754 659044730 293070172 913614156 812207712 736246312 613083324 64253888 714832340 978309312 746588130
263593382 912311945 679730400 907314976 918673560 473519840 347046080 292932588 883477408 896500944 324123203 387232896 222441344 408496984 570587870 939506176 627586752 947228944 277771590 682960059
771947264 316755790 230015560 696973547 1051079956 955974896 194747520 199303470 1036641072 610542016 871898910 475026144 969301210 854362176 927254364 992476560 548534768 564439160 836034388 646633728