1000
38900607 754404268
101950659 916668163
58498939 860772925
304875577 925331091
26337342 137827265
430735422 112436652
736260707 917530439
171784596 536900279
221843446 686599350
31095987 821655349
396506875 718609733
359569993 665949239
846404584 679098370
462835125 658939622
745558054 319514191
618078603 771386108
743071892 62010976
980571668 263412553
856911364 672499135
137051595 8012335
456561597 349964745
139093473 788304422
250610679 968818734
298469561 715597881
985960546 967775092
20014701 800748679
645558943 128751476
18766663 466586818
126448837 150175708
247030345 66283188
859314141 258224299
943528358 112819893
253964902 873868984
360057158 448810038
35172563 171485740
937123654 865625658
782714376 314838275
420258933 105096663
804284385 257992080
129919192 162739385
507187626 928013046
204613159 826891679
365646504 709916591
112944207 633165021
681857679 756769800
138158062 530819288
385374217 273904803
574973657 669159565
330779446 513023220
898526361 10527755
191595558 888649156
55102698 801193204
884902241 623981490
463421499 721256191
116730975 436775341
136985649 744835705
376669200 132138875
484987939 679499456
987125590 529900597
676279711 5650630
929780614 184711368
157188836 805386132
727451883 260323445
815113062 253893317
511473474 376145746
442987598 117310727
293415487 133663944
767143159 486560925
716924423 795038739
121365362 221533151
718510516 83299013
159279362 959541176
521562068 513769283
392313505 211778087
866397417 435257158
521839481 940219583
65961451 636040283
103818604 159129384
658019010 627457123
597854093 491554715
555246796 638732308
651396260 306793322
233978205 290028406
570444718 372136309
158953018 419248743
583247450 264468662
328810013 144550168
815037837 525948598
385527092 932729998
826751967 350626326
286268834 493749026
388898844 981740295
949836796 238907137
294083524 787502034
580821966 416622764
78411660 342984529
147475475 549938553
518342619 895302516
832904128 962417168
888842061 982347197
459754554 14452463
554270003 434845636
183386076 51011815
648904209 384196020
43303026 27539357
467026975 949381324
750755776 552093705
385425865 338905055
777084924 900482810
527581231 664551380
120750671 890248081
633209765 137781799
47359320 580260289
407011379 125374310
836186537 386746581
72083990 767732148
204632136 24470506
518688318 391139658
296491311 602121841
426534095 253310705
643452365 805637807
65751456 787359881
247665027 530471996
398146750 146647941
112306216 748950663
825446122 985664877
976518789 89617232
269914135 131820123
940274394 978918701
606632429 608335742
63314775 20207622
396324937 104940442
642253987 114430873
34253754 570649990
903685720 375945206
692668933 778463405
408361349 905641988
596518050 865317262
428430636 422986746
92611389 23562811
298662593 838932455
282275894 872504541
478114481 424641579
70014242 507280431
585453272 68925948
333005128 439239166
555314954 541167586
506477604 592190896
652824971 23252538
437606887 779303098
19385751 24403383
65578997 678714152
781494235 187279324
664554342 815152153
575957753 2400644
650578821 252132928
48205320 151062362
66623060 225457765
471735058 789187169
188692230 667388898
520821141 951921262
875523204 82026278
836774658 111915688
678565353 753681973
42758977 973645327
581597446 601980197
584085802 420626930
237259998 746750115
690138894 436682872
96034858 785136236
899131180 262816536
885017047 746017749
409096252 887511329
830634371 461186628
434852328 593198131
2404868 646875572
653028686 98334915
597273057 926618420
948654464 115819163
262631895 40017769
987064323 556946263
655251285 549607688
759653203 68955369
973629696 701598557
430341470 366227479
643539760 407200966
680790532 271997176
535201393 345184056
240870302 28946298
890313219 627529402
66114420 877893087
223817819 701450213
667517509 905002811
640263072 289408106
710509250 157585400
829700654 975331212
144638483 585799762
364000022 206968481
781615185 842486492
819167388 188364694
224488203 56915193
985858232 682003304
424886210 729045347
561583509 258225835
739271276 482505383
192904725 698631687
695575028 758281639
376838731 160842934
28389049 547256855
220030464 707964167
868266763 620647169
434651439 862873822
838104497 356673857
191967880 380054578
516904549 98207241
244725233 221141390
221076053 926251870
23021312 389056657
414323364 701789337
998537090 472560749
468801256 376339176
759412216 869946475
21783978 570648010
469198869 280829030
863666922 274416534
921067329 203580748
241514648 814613493
796155160 374294944
873745179 534663779
696873452 653681658
53499341 709117106
237331775 297615750
789843837 55141255
433785418 381436033
5470444 36717275
658931833 754331839
920073041 912553083
536916972 115488295
669860566 429936264
729773047 243556661
490034456 409428472
664041891 461375863
723729834 270564628
116542507 107649553
131830931 563622904
362906496 391259706
700783307 327104790
120421062 136847804
79419586 155990963
118181589 733720440
481134298 801657448
282075832 238505951
510236136 71879586
546520625 925710202
190936502 524881442
18874419 304899427
740318596 348931966
885864295 797676490
134565506 445593246
966935208 144849009
566128216 108875840
600400262 472735537
399414686 677784437
880825031 678910066
17123941 14901282
755064545 4017590
50429100 843163520
123453569 986258959
582485227 761358492
30402824 979856037
210000012 118009559
860377864 794325297
373751917 415906407
802202828 307567748
367334751 723066580
549795021 378817281
204227242 761595772
40897085 408904478
163547783 413044752
842174336 495411688
193872036 491665172
96916142 266906492
290997924 934096483
627405843 837492110
848707740 109337001
714566831 620567526
278150039 103121127
114432695 672871646
75776019 712187635
702385682 749762022
241723522 560306677
436112604 186334720
91081 39623659
242377702 932164164
81422788 111048997
696268084 379072604
684664769 224997578
822492797 227880201
411987713 215977298
49318831 853348509
504778554 170273033
693643113 969703295
20473111 890127506
157528447 417621162
605492406 708140386
802113913 71959086
503659561 193164353
828382484 18005422
981244406 239296461
688802496 405891808
462259607 571103990
209024032 48789008
637868027 222109571
979341965 961550493
843492355 461601419
128467859 21344122
115035909 72448253
136216947 75003311
988166477 667763737
997363615 284250838
648375447 652953076
538264898 32936862
972763286 373797880
297759157 250642507
954035568 320709474
938053898 562583348
99200063 371372995
72503429 297346371
275868050 269199743
98801950 173639801
647175146 812489808
825402881 254941799
170420286 870320580
989500686 58162358
658603639 403588539
715362138 307589024
816141301 869605098
979121579 727714933
542380552 190672731
46475008 482235415
946120311 580363499
326739719 60517759
154078717 163711946
757558436 843673653
894710983 78413566
933387377 790915803
400777463 894052577
879366456 689272227
87720740 544819102
126850171 114600661
730563799 581337016
466706157 38312778
794166032 607415939
561463031 620234995
32197311 396012713
793266483 237048147
911297868 535771815
560226036 632059905
862455567 821251405
103733948 333138215
569201112 288564289
456821957 519264773
460798825 847712380
398359417 237863791
357779447 2885324
790576121 70849098
681453229 20985936
627852442 363635732
489133096 189233920
353506659 100483929
335559420 78184994
593013392 113168446
729838637 925984470
122538771 640652538
91165111 848298123
434267406 632054360
595417351 54346631
274169434 433003575
962464128 593912163
121591554 888232457
397516535 667768204
854165448 417426264
209985591 206270404
58950304 686915132
439000446 11763871
939679024 484788710
272185598 989413383
16771927 192442136
502927196 121063864
424109475 818627755
75767348 970531780
736318424 385756680
195516564 14410000
211768176 385371055
409887612 979205589
9612821 554004915
697806949 151540256
264797737 128412220
941116343 252134483
136489279 337684484
402804049 250501538
240550047 15750874
587938053 365581462
267003846 367793186
110833945 859994509
96578788 677075795
978162375 839873848
480673628 460690551
518225085 881096476
22100039 8331439
85777822 923773458
949182193 222566060
675439744 877483208
338378075 251612471
278624620 199993405
720651447 424300971
66149345 154733640
693128175 304697461
102469969 663978513
62216223 16100251
654743458 512838806
697599766 95517490
591295406 181774632
359361497 354575846
785732548 440473580
531470624 450123638
199183397 274300507
900751319 102608181
821322632 752571330
874799006 908820106
994851222 312176578
187893577 128912753
188170606 194857681
660499809 594098936
709192739 267938999
604936353 587836355
867409721 818515730
563944058 290206856
77230379 648253907
138267023 81374356
146634216 699883455
344878138 490097220
180296529 246000367
603628293 33999756
552375741 757635408
894932786 295258740
493575286 777484579
693397812 2327958
454178361 620062078
137189683 200413346
227628473 634653897
171253132 459880154
702631965 147185986
400912207 288246678
818781565 817442169
66934975 138871489
970734441 297877205
436144597 834040153
533231459 538008590
18264765 930498547
359310176 947133361
345991768 385172277
547203146 710894239
318457016 931760219
476019841 753358989
781218727 661209523
551319637 295137926
405948193 377639200
335516814 90219364
692530133 453276315
535398117 488580699
206119336 541029037
259079304 94313326
557751858 556302070
245696665 70538744
31485246 779489449
659111600 449477925
543913806 521431822
559513940 301238902
71064598 172952063
86456454 696387648
439562492 145199723
499886647 558934573
585241503 570574038
572478156 165391290
996778572 369914839
462705569 387414712
100430474 785534105
381440388 22841291
241070991 362703706
969290037 837759214
751192265 789599215
90105837 319061484
141042262 530601022
155430356 810913512
327382412 203051714
44720776 67225815
770340211 42567435
819093405 809574913
59012934 784157755
293557016 111456899
650134261 844252554
615022067 18250960
220753317 591413955
486380189 500770347
533616686 180111045
839138167 759916334
769210268 653343747
774180183 684165703
453249456 755649285
33600520 281169462
95240028 130449124
888737992 819996304
767978314 669606866
328756937 651799103
398285910 247621519
747650993 151158784
210512399 313555957
227842074 106703587
406468922 898904941
796219411 756717262
114047055 861762936
211904413 831014650
46023673 579218727
497111343 304379509
427780506 170722211
524045362 974532767
603545030 284645030
377773445 572744109
795694275 563821312
922157562 321359657
805587727 559118611
519964887 170866799
456938970 583817047
168131159 452210481
276142472 279452375
459487782 207892981
735073328 334590898
517748201 824013458
615940640 554805658
528368563 602951862
938089558 118592601
472994961 79771235
7446792 774062151
344621311 427075693
142849053 41636053
418981232 275611390
704425394 242814726
859199691 688159762
652296342 92269552
818834664 632771067
374122191 673292607
698506007 83012574
75386387 304219059
113300122 732851764
144314447 346182045
358761253 339373387
78970915 278537061
357855589 711861698
240951140 780815879
253514103 706035984
25078169 345587090
712639340 45372414
444744318 896895912
645560267 999571240
280774276 349970944
899368975 300372352
318776655 504387303
809254693 799385291
35082807 845226427
133686768 477841442
813133512 235831150
405209541 642056818
18846017 140844809
877308143 59539197
606756633 708263463
84893483 806297047
731873653 86935926
622686765 87833705
597698995 750495033
685394969 917745649
47607779 236671432
792744971 180628480
949749065 860521998
14120081 290562299
292820700 663237130
935538731 53052571
287652809 989863247
305940945 712878189
557410801 827145093
361406317 385231443
333738087 738421989
302860893 50903808
478772723 213349569
895116787 638977152
513038226 401765369
153777653 738921646
436888307 263395719
365928221 72780732
737826043 165625588
314082713 416434863
748762178 685248225
96564620 231378911
602278805 743212415
330457483 385119099
863119474 90439959
508699937 877804548
429626766 127230595
887923532 541495502
702751058 483605939
349549822 303542914
467047514 374970921
857154973 275940254
6531061 14828413
854347651 260123379
375068839 359967194
79078015 963004965
81630890 764433023
678329426 6693935
569913961 262021695
969568562 860917725
883315460 494711297
91791947 504718928
123395791 56837441
156699193 748436862
619542483 140208269
879364495 317349039
956992075 120617480
823018835 972589313
93111079 149576171
124936063 836897765
627198605 14959359
457471874 642811295
44006995 827624740
111123645 447022538
77481095 828708813
787645191 120973778
638871015 792928386
366846761 602160504
422612585 782985053
237211490 921211217
370893236 499680141
304246757 285102919
259026341 163100118
5332310 199062295
254445259 252323599
560671568 233783506
891440363 70936739
819101410 241724764
462065021 580742417
751381261 398754544
85268013 209547883
127980360 72359834
224482140 254236890
106336253 285171643
556348572 635338009
593529097 235019400
320119095 951877366
517476928 590302859
870612136 952859092
284234726 841761825
122108704 981677355
28454199 250152954
80966147 246762758
17660128 767120285
88450665 950553732
29392771 634718177
480197534 539309144
407526967 138259317
513766817 74024266
861424902 742552921
827236777 722220724
911093613 234246498
756515483 813192453
338773728 690008762
215190933 14191169
760943427 270750302
106565735 922256510
763909490 611554718
592935444 40255593
717788602 857680032
601920342 937846719
6723166 296565470
75106583 731717589
117127187 78293923
748708088 226403345
257002628 236666514
21766606 225781358
96588495 94257183
895783456 473776123
514032133 820268052
642806443 797667677
315728814 77561358
986744030 585216841
781290051 822426621
193167711 465311499
773147570 373196967
902472324 174552833
261113822 157059109
904467162 774256416
968668444 20679781
655505825 906728815
844463288 808862119
737505613 696860807
540422509 211789056
27316743 249889817
862938096 585722586
429613098 827618152
902324582 632322929
878140615 702693834
21254121 608481111
573658658 167265068
405959432 99738609
668961331 661329035
1613380 210269177
781083429 727937659
10378131 20005882
476274138 89146276
101082080 721567447
761041509 22508864
296828297 762272324
366849167 679167902
278804704 369837898
220294227 554515618
400902827 821404872
559814242 785843267
793021605 621377517
205260447 865045260
59786746 749712575
653869219 325139612
658414030 376409239
444361787 432826405
954274743 56971938
232016357 116559600
725703742 163615842
247556439 606148312
903698274 995059243
203708920 77773515
728801558 629739430
143684453 502689612
912877502 867451473
589516269 566767859
37283509 734377469
75001621 203855596
809466570 109120847
830952469 871772532
440564414 502164032
2106457 950032991
143684040 333650590
869879297 815663508
343185426 249918600
573310562 777410959
972715833 380481781
48531586 540955614
811372752 748827181
844499872 122645925
170805982 509348942
303985578 704074267
768292443 304304073
358832580 50174218
803495863 185338339
657791176 228093779
778387795 655230773
341338561 267007847
142944262 830807084
263480942 529296335
357240730 169243530
746198981 497039269
336740685 20277474
748358254 827426585
346105936 184455968
598960452 86230509
423520330 264774399
260973528 634996218
221673942 351771537
43585261 49302952
264260865 764432570
108207356 394760313
880900046 682261429
274796722 444861311
442864818 603030414
802386285 379021794
540374296 36600230
995063747 242247003
755070941 532393011
961177083 32271547
373896149 319861949
756913297 548949093
551127109 725097634
92087991 18107599
559262567 233734035
747792079 67654406
487742185 411327509
82166514 3769127
178260590 503535105
836920172 471043814
312914955 630954755
65213245 265358347
443783371 188240159
180119705 268809456
913017132 871115047
681545577 471948549
714363807 612334406
742029256 182614860
360007436 408061305
355244167 585543901
574101836 970609169
15965098 897948514
548744110 59476018
963457768 55875484
27067250 113089111
693062191 111698397
243871313 969234636
441526814 604869772
544906995 739140146
825241737 611325604
274811767 506873854
272582904 831346229
965953007 445273339
904155432 437733602
877882593 757486019
386951561 848395361
575542727 919514954
466309054 964245246
890796432 568802131
799628576 330461720
857643293 283718905
877694780 649210018
947686852 746086184
804944976 150427044
394942416 878002465
938259410 673283768
968380160 836341497
23617257 131889805
95833348 275869722
814380785 986151271
58486275 438532545
745092604 391412125
651661591 805967230
938499916 206649881
441285327 577988023
269500890 828184796
731422636 156978214
203589330 997369207
472588965 16032855
102581780 318659475
766328739 572418602
453014708 636635498
310340101 887497303
150415227 911082572
144801566 487523557
675167076 983308059
76925106 42636209
61242400 873168080
669260157 429272814
755840659 491738868
496191403 94146463
273040212 328623654
78663009 505760798
705119537 995978907
678079795 759905433
502989736 157438106
62877867 306090896
819689839 757287164
133715145 204628056
89821422 485317043
490092669 685007771
910119616 101148223
444678447 87343061
745734197 25733178
11513143 515144152
905425363 317232077
425286245 756025162
341584848 684820536
255929467 176554786
47736985 706247759
759935918 32194606
953381198 641039608
56930600 46479760
119774276 217321390
345155977 963131196
909987714 244678400
320085346 104173180
16536389 937628434
484271032 16703084
430274172 212812315
397673095 567887998
710425932 549607654
229681468 423449847
522616717 676354386
693512506 384672113
413299019 115626193
135077462 108632919
474562886 112171245
152200539 129869420
213417330 420128190
334973063 559711556
47824248 652911733
454334475 54727112
270604595 869496276
2051215 348327862
525097268 166606516
210914732 313151264
10583870 834036350
131665008 29938921
347506891 303849394
600395230 829117259
614642566 285191779
589248364 601292883
14042062 397560505
973741443 523720290
624559417 400339310
9980930 169897646
571581199 805200465
491349690 362651584
169687754 199904966
25641971 968521716
514327709 693140548
465392359 402855420
571554794 37061845
574701122 140416349
716155339 494302618
406802600 430267632
391141258 54944068
244466990 933521762
740076328 840144028
72619488 564349364
360931802 413730045
55522874 190295996
918070407 312707796
545751471 42490019
137456715 748053031
508908069 100060005
103364343 82066187
249313398 709967188
790530959 803887660
486307057 540949653
307515083 953370953
321816023 182226080
703213975 633477045
739026399 12228292
452492691 413969111
221404850 366700706
503991187 937514155
230798703 943951534
155476512 418133567
215852840 920289969
376274933 817060919
332021604 334279753
628782211 139572041
576995995 591539047
285815406 1024706
162299581 238815439
21486093 460469503
775725995 5206172
585267182 860823028
342297532 965694138
467163471 314390441
823745593 119509354
208821414 932401336
73700834 532569026
868226075 437804753
468888935 10725930
457198601 931094326
596265456 336308960
795849088 450277183
536516501 68119669
44403909 126127319
825064934 20146766
389373904 163935484
977482852 893343523
702621390 798059587
840057094 700991875
583882909 663135570
357179062 85235790
704461139 728121701
343494610 574127930
124470967 909191882
50689195 992230735
730205893 540822885
34295305 550132075
941205550 525206316
142225829 496532158
242181334 45771947
770682029 597318479
458758741 695536513
357377091 619335286
89683063 285120737
354323454 346468703
823621564 508010003
667771496 157746061
998641624 580483313
873006975 22751061
213604916 1269354
928423220 174478943
618902123 170477826
747525103 640746025
622766798 96757072
777167625 749972611
13594336 700096639