1000
358875965 620163043
971597723 976962388
174534894 733898703
477415518 452255158
594800521 288827687
446177710 410872851
505117739 566520580
977744685 955252863
221814058 503373062
91335567 90859734
201396239 235231829
69814143 14788700
576736373 5039024
826013237 662607969
961216743 330801849
33383890 320092707
950964892 4981612
149571448 125499786
591396669 626986966
430271298 38713543
915814653 876449008
449586395 273448745
295485942 279847433
81217961 517300000
783220495 172553528
608159734 984616735
407785357 677973878
851921789 837038085
535529256 677935025
352162407 349262352
8736873 385546297
669355059 812218120
243044263 818926508
790234260 834440932
298429827 73021911
873154476 214244480
801987273 175257224
487693225 97473214
455104657 568911187
467289568 238325152
741464715 927965657
75458240 1766426
458455888 927380029
838804511 993985144
457831407 43483271
195763849 319084634
429029569 865118908
131302753 524590186
536561769 774053367
211547472 834991597
699591632 84701947
901752431 501578905
112475525 241962009
451568473 567580182
810873196 771374396
805905334 404854265
699340052 881363574
259137045 10312293
661259956 97941555
4297436 119091362
141424826 52577639
438175997 422970749
917696547 421995104
947560936 306774670
48564825 11624761
994282621 748156457
96326708 896035051
102251715 61318587
137997059 406336543
628898769 801386610
177710938 287320457
58757228 729567344
21200384 317894273
739879637 682460341
268352182 596693427
801551703 262293362
649271066 92244053
537780466 419483966
366755512 337857755
726258636 415320337
349482516 573057610
15993147 298325578
321609014 118244863
359644165 312122428
377097760 988542934
113509037 554808698
275863390 24782619
136892395 297063775
195193246 876772032
979524116 463545428
473465458 633592172
578355144 122736523
578352580 116135609
394736843 945108092
453993364 120995479
212944782 803475880
546569443 228937929
101801457 868178458
199699146 313961976
180300885 576796906
302504910 146326276
984121958 430884654
23625249 121014352
727948429 218818495
997786384 559988898
682363923 323768195
46097424 113235420
299021072 624450004
229371030 693757916
422074449 535880748
667269749 635019231
191872982 66355545
863957160 146190793
934534003 916172661
460152770 114834887
345485920 762657680
113677517 329607878
46058687 137302766
303138584 774007117
356121261 153441322
186512368 891001538
477209517 85126146
4236958 628746944
709576150 86124342
175021213 131650598
622005090 842290962
619186183 813878072
908646507 335659697
960068866 695696864
251832357 420221635
663048105 597318277
35395668 776725623
779442509 81454355
766544743 82581093
707977826 122666004
236022415 894490195
866183896 565748286
979616341 870420854
194495229 541708845
956545196 369516442
525875797 431066640
64323757 145061980
244944711 825486619
333238031 57529930
521183482 585070388
477751565 36747940
34905018 365663587
813473563 814347528
447117943 432534660
749444975 7612122
407717018 985467390
902102317 273900913
403732029 734235012
996838122 598227259
128460210 805899671
820260055 506852361
236966310 884583813
504430695 334427376
562586785 837668726
391957306 83770266
275255467 869708872
120518206 310160486
87888812 786508124
977024368 535006755
71559137 726469342
542618878 479276155
564453085 297237548
753177068 968185114
883988914 602531543
418928726 12449123
408431214 91705135
371817839 497913878
976288948 876248534
832341254 391392086
713917260 224298560
327678706 989172727
946523786 300713266
151849566 34412597
87221389 128873933
421935707 11296880
707859629 964554585
490573035 124829067
114308486 96266457
945530536 998297401
698798000 216975615
863262878 107229213
308680750 87597070
457659446 137486051
963845605 290000699
528878137 530279218
366815613 856556843
371968298 313339398
157270109 523817865
200268350 97007852
505208152 622204057
108304733 65584135
439274995 598877768
42929556 553583481
695144225 988460092
404397235 246458579
205435707 120176467
206204146 514116457
207773537 663863592
651602509 24135495
953864292 32996999
554414713 173196258
889553843 926383012
486535657 46823951
302717230 686804007
996348158 807925382
161524417 104652890
726025871 600799412
556047013 768955428
6899246 103707591
757415519 411296482
350166170 815367580
383989303 556370317
182000391 591762840
72750262 833602900
615898336 26614553
866599899 22829402
52327166 608670095
949212414 538862823
508010400 251929643
78183183 504358558
912371380 239707600
461527802 638397250
840507012 870091169
259869031 847406258
973798761 17284550
111219093 176481284
685168484 495208396
585367955 867168875
939487591 658118218
553288128 407902280
537249125 272404381
430731682 589576291
881074476 379944096
128439113 389084876
484390093 59138650
745959788 396761472
151362604 60003943
887675077 991869616
930095113 147544107
691792228 756410227
17345011 655527675
932891511 702513496
3252425 370775820
422198724 942740016
28894037 975486853
350642295 566143162
247891233 781373977
8235807 128965708
13834426 136674920
370566938 498224520
48329925 116526725
747502346 199692529
29047023 635177422
44078499 959142136
635237884 588387081
715552362 652582895
243914755 500960226
207612744 247167180
871736046 629811469
42423549 753146437
457814675 393065844
171805953 705705908
26956175 180041760
687187970 40790601
169233034 910271263
391531475 217562959
879314342 139033821
269771843 908361365
626727597 313850342
867503500 114481834
902237423 435572215
767064730 998668532
789048796 827193828
98352066 513301195
309521650 140775615
266447632 767336325
533841460 438253585
325558586 413313989
618295345 12746556
306620944 787528379
775534173 698152420
857607693 654848514
689702595 127379535
415726233 168946545
293746231 135746086
283428380 48500007
571318302 903009464
47168538 212883451
730203291 145520604
726184646 39724941
286296220 992632278
659577620 672654034
283402216 985136207
85968022 754213915
850399117 392588966
394258648 625933289
943257740 251866340
133298156 485476688
231762229 549024389
654423234 525508460
684770476 790367968
574008467 108605131
693377431 621177005
321488582 276097075
619213964 47673227
168338370 905510184
892821860 827915991
430680571 28740429
665568551 516648593
782954345 515967667
761753913 29729346
994417310 705011653
281595686 127715465
43004694 513357915
529256209 697427928
38866374 66543038
340312249 465391195
27664523 33689679
86568199 349153105
162303109 558298517
249342686 183157833
316325054 994680900
11073823 747005625
23421329 529158728
116170571 658892028
45126394 877924485
688621374 892060058
435452491 822733414
872291878 478457185
188607682 254064440
28401467 79990410
320607478 368713716
545381605 348272001
254919750 484466158
549941460 417222859
42764675 799284146
600380692 359089729
646481400 463970870
106095354 522419083
993129598 74782279
33827464 890772347
952706764 722448838
635348758 388159254
397698605 507640635
866616440 586306287
761705075 895017907
666296697 934828907
116247976 211678301
135617261 371167726
696144459 685558721
788390585 591425488
337359221 241287631
950515218 983840621
557774855 909126926
506259703 403420806
983909205 540087167
146709506 789132323
115052358 782058265
29807930 512750963
142215253 896424370
99057249 903920329
643958630 617870300
691265589 760206607
829548601 826882851
131374332 378209413
512441571 772281272
969634902 849800792
866085257 772666473
686157766 423860111
534309752 44933822
827280917 370735310
585020989 973990424
12383986 552589701
608565042 42191917
65340663 750780295
938616287 16914266
507216977 435091271
487300920 198482566
47814231 169365874
25365416 31704917
547575288 390323341
656502543 369726543
92640487 522587799
994909370 778798253
798964264 381735475
823732076 478761535
752470785 261269418
305268312 764854772
813859120 913833354
807046689 731716137
664613648 598179329
601146758 24346979
885786954 88447677
222829545 933601185
110329906 100711315
817822457 657905194
343551010 474324999
880148091 436191497
849429153 875057460
67506104 648393416
109309288 743754534
127154950 861780073
5023951 284939616
479151198 671399425
198772969 138714240
255631916 715902972
589409924 709295028
740249951 475196877
650259059 963079496
261314416 760588965
916307165 79136872
271010512 259858174
405978225 151158602
548566026 107923731
878732416 616072130
756317148 988041704
212343017 735988452
702338131 69883322
20928068 34005682
741282748 72217391
172719923 849431018
788120363 762129847
558726045 380886667
89843077 61501457
196482516 203673847
822090423 112789680
135327073 93100934
225164209 541305299
96775891 773730235
649229030 975508307
242318718 258062531
963550011 454661735
846567338 518404495
524545057 720011760
552410177 118344158
792229151 725130100
967775176 432865868
339776300 379017574
813752535 282135732
440519032 10235051
485809579 262609454
975541086 621136653
208226742 200705294
14958305 305002633
974435529 664187335
280510940 69270600
774766221 96577304
523932335 621333558
614981799 48477392
193861671 19908329
166821550 986090822
745038430 134596726
271473043 937331084
366130654 937741933
219466815 806649686
800493338 705276395
69259139 776034423
178929401 130002236
829256072 193887706
435004869 656207954
858075041 715515809
725478555 485357615
664609467 249410889
106691172 132107619
150404635 153069197
152015949 317226186
139160019 897054379
304339266 263149416
686901816 670469920
53407702 906368632
329635960 853901040
464161380 251411453
482451817 643090781
381413689 311707888
836978487 816418559
967915842 547569881
384450721 545910750
32927496 49060188
795321640 992135023
181167807 945726275
145204220 333183756
115468814 136880593
82754488 272324434
252546363 769656305
942794355 305954066
528541290 124946668
12371459 845219024
376358121 494823276
340826158 757771811
806531164 30320998
574190369 626963360
577890879 958641090
25390463 463334729
860217632 820712103
307986106 41385439
618954732 305706680
227085549 586939900
295103627 162356392
859264335 400166344
932012697 654575043
706120410 313070340
779521711 718491870
10805717 155879831
65831499 351631875
913651642 872362664
381952873 340358364
351842377 959843752
151515808 377232840
275694835 11733439
50461297 436197295
905635233 521932383
741903975 985237137
108872282 889523956
147593528 968136617
289690299 932122579
475228013 848327064
97709272 254749723
419335287 108514989
263145909 485166786
460146864 29313904
210045803 842099737
369672269 561888180
654459842 373704431
791637375 930154677
237954224 842098672
218868325 143589457
216547408 960772300
981342948 325419690
702812609 128936475
146072661 992502909
913575408 621300674
693346326 11284679
728566752 112681612
119799668 991712661
597848398 579946532
21026564 807894202
274562622 243215187
222298735 929022464
616919618 13936109
711693495 854873843
708551135 930561820
850979654 925098543
743850474 832322601
103034587 446663082
813775430 101623602
291682344 579867191
722924276 985028670
591151870 304007381
950226636 563467892
295720041 400591388
143414423 169262960
61001943 270493399
412478147 283300678
199515862 29397765
149753142 911209357
884271608 710820631
694287531 587767615
488435528 438138004
272606569 591470115
737317440 86381998
693093717 28999784
518765543 268534346
866544808 109917412
572541728 669287798
525901658 720778123
69879185 521832435
890041083 130881128
792325834 302519230
266698160 991841696
184433349 416451302
755567407 68704956
127271933 302371291
508988925 468223815
740509295 781595494
59693929 330343088
720493846 605304000
211859226 239259388
726354700 78404034
201693154 151412781
600208186 727594812
872190905 670087371
101943600 762231987
653484853 894269434
917267571 920183013
738627483 101700919
189150669 346711243
22922229 168938956
649082534 531911154
637162771 242108182
166023001 549373054
572451271 886516847
7193407 784310497
125776234 733548107
715230885 179985742
884960889 315439070
760096908 757151793
838042795 862040508
371900133 491527647
756309941 141684058
264227014 347453778
243384977 453377683
694165021 118823561
622316639 343247555
650734715 259479409
585355737 816757717
808852463 10323361
555790917 816045870
794633859 534083506
402110330 509864743
714069248 287071218
677820168 326682510
896739365 515862962
188723017 121155852
859906964 797549313
262839910 124133977
145003090 506224887
577511660 839168111
625048448 52344652
34932019 128299517
311824061 472804111
797573588 973192878
483127472 353364504
641755101 277761330
887448010 43865430
640142428 454033612
183453003 317962595
780716122 80192367
686341911 821955493
201348219 546248874
619504805 464188129
522899205 617024249
822929371 100410864
308708714 300494172
5271870 343640733
428793689 317095931
816444844 78883630
142805162 152088670
432248135 784560263
429850000 172212498
828425694 69992427
478762464 11878696
240471376 111994939
944587418 926813288
933950433 145935637
325578515 405971591
462640120 848477721
22995840 138085844
801404939 331704554
438580017 806676810
527861641 867373706
976289095 196822839
946257337 119094257
348911509 231021825
903654520 778761509
255750677 584596567
701270291 734513142
448991617 794258021
846508081 246095389
573587662 780458513
244547380 899166178
38946458 707187500
600160252 61942298
845273345 254081544
246163206 136369715
913274708 774024847
3743420 889563803
970847686 802517111
861174414 319759194
886055290 617345287
951037058 141805967
54458208 504823702
876319109 503449825
299081722 575343543
749545214 872669385
208318410 994092594
624351916 247264868
553796448 77028521
309207166 251586146
183626419 555370372
387955861 96901127
181911572 244215635
838981284 152759258
899249101 700155697
325034806 785304390
170017337 276071863
779626711 224475545
780895565 508462173
727925371 932493642
83805716 329986938
657679380 292124126
176595886 134547649
539388994 582908688
211576170 701112514
834494834 395202589
108999239 74967048
344620070 290910811
171699037 183601353
443670069 70948137
736273404 768704876
708768882 906290742
897293093 488395592
130766286 530705012
996857766 711208011
463198653 933179836
41194949 120878032
77820315 70307189
107942035 617209309
653215877 319518205
170838176 340227064
567237148 279837415
267710466 911857219
570748226 439409503
95458571 14418295
510357641 684248330
635639525 71642876
590539071 385448971
560038468 573821711
916153983 409412587
285029722 231868989
195108776 178741025
205263375 272929091
101564568 313205410
890138400 754780445
632723615 60976575
947523863 52477117
193330344 215234328
964334336 764078571
654643831 912309261
631013220 17517825
596557590 119169098
89160701 39613014
504618069 501715524
613434726 420772052
911128111 750980802
652641041 106236887
929721827 857904417
231682332 31286394
23626180 121820732
638583193 656349796
35313661 438623409
708826913 81160360
653857737 525677602
845238931 161017921
437986862 476252150
31052101 887060807
595421248 120212802
926673821 100039316
621928326 392624900
373327722 385572791
143605701 878485118
344326032 925843882
588905888 576008364
809646630 612532068
550345450 300746176
121398217 438175466
739369585 830225130
519335826 245743675
208419085 217091110
259277951 646405948
693343260 290330052
385983108 141280861
410542854 165173282
93836531 884987535
557798183 319680608
123076679 553920238
198165725 467402711
332280474 787071613
895927429 994443458
252120034 298789233
147705988 373518252
736964699 887075573
56259735 108816878
985335603 264678821
325907988 244613553
911084769 871767602
534943605 149584230
13048462 798002813
314757512 959401348
682990347 872555695
279081955 806067026
278992287 329764034
125986090 463789115
116835646 21913519
458232572 221472035
173219106 605938560
594990287 910183805
345530487 651250022
871517037 183382443
915928843 49941378
427995996 679529965
921708980 815455955
829114195 787273796
613458767 143871707
746675143 148965468
868943756 878273453
807548848 452396
208037486 933534939
464241511 177389487
807964812 922474084
398861522 981183918
380928997 993851809
743884076 578975838
497618184 467917466
762358281 413547027
517858844 42870630
93076991 439567823
858326585 774707541
79357972 324301706
918579248 826033115
473267174 640039357
556822921 133332375
640491754 764860408
66867313 104733264
794766249 727348479
879723702 46144124
561048750 113169053
39995932 157449179
692144891 390130470
625366645 454503172
803677497 143225488
497373802 749270843
435309665 208216741
376494737 514667637
532518447 147590338
193217106 5785620
787629695 750040027
139117995 428121448
367416788 58501663
385371067 14699390
638366496 265094768
60843514 51931600
378263821 100839446
61897133 70408712
343486271 687263779
377428238 147163767
683005621 727318394
748950964 970831641
935535135 125445700
338015631 468053581
125552392 531232737
326355555 913182088
133789118 317989905
193819889 353722260
229007922 579190956
368421651 719890772
844285725 429265165
771822372 75065899
382620966 833719506
997990966 726107237
373499638 227935557
725787358 909021613
955253952 327254676
879853253 890789086
305216730 70385238
211359021 430769123
601617975 390230930
343951210 587923447
708220835 537771099
941645708 789745111
116962055 310067358
509635883 813764134
739332523 133974608
741346387 121953488
820210468 739337353
700577079 46226459
967272910 426364437
955248073 775043215
753619113 687617679
518348655 58835842
758002917 729707676
342121319 212137246
119938605 686072529
800060693 680675795
76359982 741706400
322937259 45838391
904290112 832573142
712118879 496138989
819064105 453465265
470608831 639274572
45318971 171185910
685501032 865108236
450066701 493265458
640151450 56202167
180883136 11016458
115038009 938886054
740724134 309675683
3539653 713179094
995748212 803600346
246371242 924624548
397823100 569308501
970462939 302113211
254397997 535098171
798252200 73462101
988563437 121377385
565253027 886398762
292563295 103270412
751506997 742629996
596535870 244174801
798832163 629935361
255191259 766386526
421337768 848431748
76062208 424877421
414127195 924326775
228477766 660498437
701467676 626300866
82323291 524446969
780930432 189237642
59545139 431698985
115216097 900624930
553076370 680469125
787023692 845639665
636255891 391047042
440786014 85308115
487738197 92134530
715243476 742929457
711037411 136581243
443877558 639615973
561458664 858004753
416459101 642452784
371019543 117926777
121270004 453342834
642373746 902200436
642580477 554435239
333899420 757796574
455060169 886975791
290782052 94600214
585131809 927037944
338163610 878434178
12346058 825901808
970568708 580105888
421347618 534122472
716687131 865225176
173738445 130662148
723229928 590197546
773114932 94249470
560640677 894384936
400108658 55530776
649101725 895205489
609966016 983001146
505518417 65026184
722493290 796300469
12142752 160141452
575854766 350306362
38575629 440717178
28724523 861660692
20823065 450072141
248299517 590026550
315297316 422037962
573205052 891043598
864751863 198836338
837809422 425392539
93221273 90434434
480923316 594839353
985639923 90889331
430356852 491158339
8431869 5366495
139975162 873090976
165507947 568346282
75913691 56599931
9063460 104638215
770776977 882402880
554710356 19076493
324945784 870007673
293630810 898150836
613567624 158382672
96987173 451377046
436291565 42724801
541811480 917214881
490080508 379967756
860620566 920437360
871126096 721568789
925803855 863617612
447176118 91311801
431963893 523089810
428086 293543707
627728025 771205063
28462941 182438380
642797911 205925079
904962407 936428721
104075914 518530031
94811392 53579442
822423431 383619311
948820598 216751264
153350546 291417459
596719020 13971111
211854818 320361469
588056255 137658672
183979080 35232372
81486827 468459328
410838536 934431269
762003035 38566560
558152685 642982330
73521295 200950595
848907409 978483702
137379315 805499678