1000
662901492 757792097
22571113 205360684
341580811 497412615
141460200 418808285
281598247 518331970
823324435 560796228
905571827 468481104
496729667 241030356
677550635 167965278
766471766 91910974
360589822 8842436
643190824 109681851
502897563 942907589
387971098 146626782
748081671 140351876
461828657 410983162
750660327 336916124
468860201 92241137
834328739 610320401
363565776 115926985
128652370 39406565
529239567 886740551
507887669 25969233
127770906 37954658
46450865 746759026
129865632 407040687
755601463 625572811
369238892 258499025
568480399 757209991
405125807 169078423
750078221 866954464
580061586 353254901
56386941 48921786
298012392 890715680
511758541 514094523
859159019 640410911
553501088 388398585
379667816 61388756
266884172 359955076
99343414 313335038
106714102 81725401
720375725 862315565
707298212 89614617
973330944 128294964
699340962 230973105
297373387 301935536
97927568 877434973
507706791 6830864
778873113 805719183
897546544 143148007
172330059 756705563
783558919 725831147
997620502 15743088
787219904 264504674
375698164 739079672
577839712 482412266
820805073 150731790
197244184 528103284
92862761 23091482
656398248 644720077
254064587 953771636
946655613 204508509
683722962 306878757
211339373 315112429
112597940 108885917
458260436 137444353
718107834 94335708
863275501 715728335
110078796 503011758
832749363 485776961
242091429 263105428
820705581 62896502
413837219 17949765
443516140 359216334
41041247 952430743
3936411 147622188
758718732 803108378
352130697 294958047
109987135 563470071
610070476 75101429
672355988 920847267
212545782 242980175
15182974 75821282
958708510 977778126
431349394 643974227
316071440 673440824
907079655 136777020
588853680 173433227
7243139 884886174
532649562 900800741
837316916 536585973
48422928 448552001
192210704 400553626
743510049 302197839
964023697 206096878
229815622 488896038
126944144 442361405
731876213 994643474
370699041 543101076
972421599 802048436
39591656 141009392
328005613 946671312
277786412 769375647
120104538 137545906
654261820 652754100
38346646 344095090
41856426 86769575
792647091 234067131
339839555 388673493
388781324 156379605
594770372 618596947
497791997 721714516
60958351 82184563
568874343 284173746
625285639 393812295
938738536 664877296
534821687 119260502
464064961 812608100
888636149 584169499
950154006 395414323
89439953 841017006
739509413 131296379
780302935 384672857
217879864 120142489
773346351 606661189
129038448 220633076
77774489 626830445
942347592 138732840
709015008 363738289
275422940 186817001
757550584 66677830
704210651 292372271
185938332 168275611
957496725 74574481
604961464 760167084
469988804 694401417
601184089 62014570
678214151 234003378
299203781 748610369
206662221 72550131
207787911 335700670
145699561 285562400
815047469 88047153
276811594 376578831
304301796 552234535
563395832 61852379
618912365 120122836
206741004 804850697
288398447 164237728
731941532 893359911
924404812 54446689
440277682 378105255
116461259 971008187
612108633 415665041
719618555 818770854
340731526 927406467
6987877 486431088
65485220 822035347
426994595 342296815
51130531 731296391
894531350 614526363
645665124 365960068
734649199 852406129
23327118 875564000
16643856 755268651
621440264 793565023
809715340 61717945
24186631 778692954
885242486 488811618
46874348 457377395
160098825 387605874
237300215 167086703
726553316 302785435
841638404 6064264
645082250 892768935
737360655 392129953
359811651 235542133
758090021 94460849
87948261 633933494
822541203 957108472
241718498 443981466
603189848 51433837
358215766 627376479
682643145 95974605
116188096 729517493
553352000 128803276
117123367 790652215
295889979 696193037
93437650 137528382
702257302 738519900
882813671 292134310
130649853 242625321
527676443 741256228
189602524 615624704
227706075 12143726
425249530 469424573
308641546 28439377
373374765 519373666
508332211 56017909
615348272 477036661
785535403 168700271
605839937 755175124
959352487 901729916
303884514 905306491
891774652 6141815
496342744 627104676
298276126 479508951
869729997 825952569
73281533 911848875
294093627 300987608
776508955 719343157
770412182 85150501
600298888 143786946
457040521 108631098
52321209 72388792
585667760 837856612
93605418 44024050
445548089 52957904
945753967 749432604
810780749 690044972
608090773 307123492
169666002 906366899
786632444 39395998
584835822 859913977
803761228 731445803
13417938 580270182
303305313 783830120
517937037 903604201
927617066 974977559
12235299 979938276
899882705 450419413
670311241 993488123
494443463 968375685
898962381 292713783
570324642 709743129
835275110 178415414
869382976 4941111
937298668 508531773
896853464 374650843
220962103 700614691
106096645 234380041
133401227 409401958
18210161 503854618
165522512 798343581
331348530 30274165
630798210 231231235
480693578 153625805
77235711 827653396
122001489 976198093
120367178 692326131
538457575 808158642
723257899 407840550
813099753 660556566
916372323 562469571
35207408 137334425
115600615 993820408
224230821 249001842
255738719 242440982
752856461 421261232
40784562 84204990
451535397 524099127
167952579 932228976
677724932 245188291
612398725 799726421
73902737 585282257
344568905 612360312
393440899 67826803
20200862 59057005
580899724 789089539
621526576 468623486
778940319 737127192
314960248 3171139
838645388 570698967
98128475 444018202
991960199 991429392
380739547 443495596
515528518 548692126
228240925 45769803
646396771 840639650
845496224 720299508
278438260 42581482
332659820 671879159
962924641 205377036
583452519 396340718
846982929 57495448
864964204 478439601
794622640 32440805
334127094 485784382
603139773 432255569
929802584 595099971
276201315 310542130
891111921 791729833
711750611 119352845
837499637 358147381
812508849 535512214
78446889 90947109
430610051 263623063
615342622 393534691
321516453 51311494
789875409 168499381
108806943 507355966
646938983 903429583
539796772 981066077
241730318 142936544
265838000 171532902
590552869 542039315
334591386 334181144
186285501 46341996
306050343 876301492
257005732 118559192
264330060 187968975
62022655 694940111
451592038 529881631
88474801 773108491
581193126 730866564
794124226 690000069
90738883 293579562
445946005 483052009
127161993 687676324
478504907 392999993
711725580 69057776
787555662 46316965
255755274 973841163
92658962 561805617
702659009 202181048
532881163 966989069
390150023 447420172
661929179 841742061
977301804 602920334
467366905 411011283
186303251 114007484
953527706 129558488
407587047 251990064
612610498 534749040
939666388 91115404
927749033 503908321
12689534 567821048
550225287 268444808
394178564 495400603
830250426 96837572
697581651 215647942
63826640 87731673
663068115 578272173
781990088 492886272
33708860 101873346
903897555 72528465
215880830 709941614
202086954 623467877
961931678 814697452
10733270 754114420
905812856 938482303
258022740 771018745
358819704 660764381
39463552 752998269
8681337 722230332
849835841 706262988
937878275 766178836
646511015 453462743
196967362 281017456
946349015 83192577
235407156 702762923
155721042 451287987
412704536 357807996
927272218 227152567
172505447 938005489
981266987 930834658
729004145 91806081
701853402 87823849
752570462 593833308
840822118 761251800
168579994 543174312
320031141 958974623
161869501 966542157
412437365 211353218
100075966 211302733
294545795 335483123
914065656 450266837
639287464 179286545
808074834 566559681
406439112 980580281
357081523 387706099
763931292 86085668
479512180 318301047
26425871 84598995
912134356 867247989
845850795 933230704
262938654 165881936
892205326 277324510
984940447 157159044
488677728 85016412
368461777 783223523
273015889 135043786
233490359 912303353
314330331 41565192
331379388 720769443
874661828 688460911
108475541 491109473
627062933 440504075
809410521 653488804
525103071 574061230
373253146 223470219
507291933 636191801
389352155 252013612
913516311 226808955
261689010 254710392
164341722 630150787
37933914 437357611
765194573 123940627
202177318 79524903
18022174 386073060
652810700 892684002
74533970 613802596
236309828 554113258
54306670 45720348
207602061 431926095
619781578 580855208
655396315 979589865
69563362 897264824
84119830 835596027
124073779 345808840
90306418 288415501
975959627 128240332
578289466 593670553
104697313 780466784
525711810 122719487
19056197 31038864
15403488 93590168
644841460 104229671
500219780 551664484
149950019 707821841
983590580 622247952
141193402 491503248
601837816 63273118
241284425 685957647
898869145 365358204
31766486 989175563
506290059 860242468
969932249 84579525
306429374 74629562
717562663 684657539
49865403 736618861
715696403 65268892
682725383 360537862
22014917 182945162
912202346 171964936
743283357 748309279
794212888 884476760
92328880 248567058
947749878 333613306
787041059 699135377
551487864 671323899
540827293 57777923
384082720 363275896
142357448 690512095
290421812 712436465
227685987 340287215
449055325 943382390
258072461 131780707
156436605 280087378
167242223 68638950
452052315 910525581
669464584 98781556
647518694 614309818
199864968 447784925
947923124 986906027
146920301 351927342
658229926 540263949
409705265 42312645
903539845 404579067
585341094 193961656
117015531 813027081
534248871 418587211
608925824 792321333
402884272 765362429
72408710 422642850
686517734 376977379
185684784 208498671
328275290 833203478
822808489 528140258
133504756 623247967
515046285 132941412
975175309 25792564
673205361 237396927
920621564 429261559
641975994 358479012
623223215 611507879
24022446 9988439
882611444 632948271
654826126 138012070
398310699 579751191
560654920 84828432
956728570 746339704
145843457 137520213
432059535 968651947
665660472 565564291
591899913 33223110
551022057 419591575
59015674 76743771
656988502 979637238
506005330 151480849
190632603 129228544
762988728 214655050
991733339 498116526
847603321 646559464
636128596 98430373
78827008 196783515
35775160 35555578
943123219 181618617
25592145 227699107
150270563 691252617
793263398 594686830
724475727 196801809
14278404 783491401
273545580 671266906
615644993 779550911
822747755 806277596
761295809 438252837
20932645 753029147
936369363 721052320
252104965 425014312
819482694 330931973
621797827 855257854
219003905 417437399
36876470 244596051
645136506 39663388
935848668 290916257
634350218 512840749
487718066 648628623
148848503 761263647
172411882 764493496
393330911 847675992
423287446 154626719
138445182 296736445
760172221 74814544
17788765 12277185
352345210 689787813
195725512 974143037
545045666 267245772
244096789 434438490
511841823 741749649
474101878 300206844
32665905 108452096
813047593 372900326
609597073 961896097
986680327 782008955
578905946 380011237
482201300 854709746
387154310 620646482
3962545 147326530
547977380 21751310
12120069 900322590
564055477 60361936
726981980 109101142
327607708 971078769
396055986 839449531
565344771 870157865
992172729 450527031
978609961 657736676
823427357 440723387
472149126 662624037
75248695 51055071
42635273 557449996
758281172 282305937
178096477 762243717
429632468 726073858
636511381 294268891
478912801 200566857
354630827 205894781
162184353 682238535
29489903 558240339
374204419 594834675
280914557 366377148
45361705 112040871
24113823 721305416
552764258 348779303
236445806 628012954
252350728 131597433
185462949 10631899
413903370 216075780
772875616 843535838
942149638 261903350
137804729 273578793
462470207 344951910
479473574 477170914
27190445 361479831
35411253 401394864
956314506 168842164
620288366 854192565
280883036 496918543
428014334 833647294
845697846 664460140
461660247 98048574
796057573 499639550
108680473 62477297
715715331 734072444
906013135 510381322
995975794 896334218
783960115 310962355
93802482 115950042
788133269 120992927
477429874 676060876
374904145 286260733
844903041 995192512
140453298 125786076
492111054 420983986
811949724 190325254
937960481 126126325
288373828 586534407
625765875 249570655
649011704 341481205
836159453 407541193
851862528 684651601
156391764 488338996
995613956 250194246
604289039 636263578
371187173 81718912
164840808 746091319
367979645 862260203
593800184 360949297
840562633 85911237
634449638 652512356
128752845 572410118
778638681 417126673
11460878 256920910
519213683 660472583
598402115 355373135
68013775 302780996
40024735 224405539
791119993 888155045
474599786 247925385
376934977 698303313
329644297 394292139
296910985 550140296
256552341 890711169
911089594 97114973
829138761 398055585
602143683 957891606
970465703 233298718
227534633 981926581
490219628 746748316
494915517 941138097
102121450 562929292
96435447 994662541
639851186 887555440
735333939 114450971
135480824 964785270
665270638 317641475
359077408 962181624
867781771 468146103
852892792 631387718
417777430 534547906
29443302 19921113
492439512 852425359
105736185 719974145
686868294 448472167
319238814 34300164
389610263 273876618
597229457 486045710
121055512 89596996
226117503 856389452
56564321 214114681
673691075 721834959
384272510 32768483
684016582 104570635
353430940 389425728
735958353 771208371
923973634 617918010
643645838 268929499
322859722 749382023
841419998 862244370
50370543 160658811
896544535 439980806
434535430 346290345
778542871 555590942
435887341 4660373
264496747 492451662
71291409 938187823
214286620 455563919
823472660 750819557
560134554 29419953
140245284 148609261
800628324 916735272
619043625 444274161
38181125 941903347
46172537 879601123
656664071 96543080
892776289 553208605
389040241 179828072
899498950 167583111
735419014 187902644
24759838 852432116
680354306 96051247
643136292 894640926
404131521 319125305
497976836 816782429
348545258 490738474
965391690 149173582
259990100 436951668
445964097 298171225
231371369 492136635
30288701 888035440
441196069 923064990
293760398 830236310
102893061 45775701
997819421 690828430
233678345 875095614
395776899 914032651
823663215 38913190
661189930 80311089
358038495 159166766
897093519 706583753
649905240 715001562
708273689 909895340
151953230 154237786
60582918 383324599
498890775 90871620
123876392 940086844
866452964 417636790
770323154 821862380
463412491 620658928
365207163 697090836
348270895 760984062
611123486 171934110
652413606 124829769
252245199 10452100
283996535 1855071
569552207 786418130
716856634 130342250
548829823 868809864
284580036 609412742
104650816 783470811
552800716 228527208
576074008 271770033
646163998 198913515
946148767 109576488
819572444 163872283
659183678 20359692
924856345 122823517
192293802 429786304
247653286 297055356
292754758 531649822
298910427 862306966
170584305 15767060
992649216 719414128
737093278 129745605
181343223 841744094
765732770 734143939
922787656 341806777
858430327 421468007
540720293 804579093
383560849 212809090
968451377 42744526
233168782 745824075
165568043 277978939
28126733 413221330
575034295 320881491
797387506 873944722
35704810 967971811
889711783 28354025
687385938 479321414
10615984 868729162
173581862 776348754
455389454 96369517
970671886 166336134
517837525 363908532
970915228 901398374
576717622 791882958
796659255 662402758
390223386 962227298
940381697 418350119
227964981 515415991
739231611 25352486
241877067 774936421
845840651 131588849
655806801 385742943
463426617 518939139
106988458 637008479
147804247 562377912
733377997 118476132
728714047 103731875
482384664 552145628
857646603 911618640
196544939 654305857
574021397 439284679
469049509 366919448
857634799 549530844
882335439 449382763
427399685 124212505
76835537 273240335
108317708 585158692
658983278 424260680
104097831 765971736
61269158 251902078
180866002 647163509
222894564 762096403
750895384 705279228
166758384 461058341
469414221 363303323
115364197 43435617
802588002 436930060
262871419 512739154
986460905 145206858
814638271 266376943
121935717 891473809
539617278 82769780
329148854 51116910
359546814 433246685
669605000 420815972
537665117 850471002
67979481 760559681
465083758 671391219
318355262 631842142
132449559 787769483
995145465 100330111
683721455 650249821
389776525 946592874
15505328 228753783
944316086 830143600
495130726 918768158
574133762 887264359
854054292 903282616
938381269 213601105
189045655 460502622
486933431 726710772
163489978 407429266
339786807 628573736
78820485 658142069
260415878 63786398
445911552 108077696
16632863 129633006
610843871 258925743
928742234 626349200
340195880 873058320
309009153 835326607
644342831 735659269
575107319 498397122
491458238 366004941
564514581 680503893
826507563 51448011
259731019 989997541
458877278 599517826
618571277 390214117
110176248 731503509
306516869 556087800
839581205 175666087
538237160 302941430
287108184 319495748
929290630 627304064
45070421 90816136
315147024 689413252
826475405 890254343
40326727 170449996
256259283 604841308
850953890 82766846
656289319 963201263
925280741 967682951
415235442 396368371
210413421 525411690
127871879 516930291
81499490 819969439
545112732 472253004
122910868 832220916
791748752 904717852
459524979 836819173
995533988 774672004
378748778 674525746
517442700 419075505
844975742 773701984
23916812 548445985
708985184 532722486
364163601 486782278
500405436 779399043
883150650 710818858
304810733 11022528
80265502 238826577
683508321 625378234
563595935 806419189
310115503 207861041
563653394 769640482
44680213 411703735
396828839 275945346
86229480 914271540
695020851 783721577
540489877 718937664
184683915 101991414
104176503 548847517
588773692 604581939
180762913 324440695
167917150 485573646
187979578 100699006
576916577 871487899
726077240 140512512
530423442 36192742
348373553 94076835
658349579 245570120
505780571 907694772
521515466 444526405
674482665 69052671
80764335 67488895
787990335 117964605
169480309 892166838
666812122 610770356
349265130 847575035
935211051 369698635
185665035 123190628
470397641 762581612
994678528 48991235
755610478 377618323
85183977 103984030
471695158 596049910
202070505 829992083
356261036 576102325
127034842 30743700
645154996 207799177
98232596 285661684
325763782 120229259
30344875 845092258
730999615 379610006
545183647 666210666
749308641 730848682
641917648 72222635
345946647 489112529
121213870 101557125
866730852 58914202
58057509 190942364
654964112 112644368
20934446 11225147
688746694 147969288
894485203 186418043
208284820 992717799
472079728 534048602
112947057 502424603
231657214 696463027
882034609 776840861
215190046 483859603
360205896 857107694
556082239 706152543
346220223 677296109
660226022 65467428
736210311 570799886
256409792 243690777
535960608 277344239
107432278 77223655
277829881 1917480
263641699 486114701
847151633 735721427
20163303 812615045
238146029 104336871
361594425 972696993
881177732 576784471
309072949 241383627
433892164 865155188
800052524 632628741
394967651 312794900
698096170 983694316
883594786 954505962
79901446 272071747
84366554 187333725
349295403 362196436
41767559 612937102
848311137 741435547
348658528 720990794
406566945 439320911
825327665 768161370
412017903 706505396
344945840 721090853
800405377 631354358
438762394 600457901
263983099 686246399
913252801 962079269
669940715 649363940
769101584 749842161
921435687 853468139
789692240 123247443
215664574 831459800
736184545 63975710
425411700 84843072
637482859 831978645
376680338 462810523
600140014 788698241
21832273 797602208
362305447 822237650
428956565 653584196
275211904 545456018
339830594 40981058
360051640 862287663
542861352 129153224
464646178 316813393
982621363 254338417
440060836 50802290
938314571 176245381
967294355 363726270
113604807 604777213
48221268 490285145
920104091 648361282
131499740 941936364
298479843 346321541
616690367 727436409
999905737 744418626
125408780 192252685