1000
3021544 383844645
150777033 75965531
173194118 287932285
931104466 964593235
69625941 905448292
514521094 472357029
182096700 23358183
936557540 411395899
48829099 950696438
748774770 209179989
356966269 177449847
139411635 714648563
241169494 205042993
43380033 100636653
114975527 764108777
52045118 970513426
469775 55338505
46478956 173663893
195787144 977583422
990773482 265413086
735548067 505294576
737770115 917644768
381169113 526844008
181557020 282514567
330056799 782848144
491694556 687023068
960297991 631106191
254187984 53983838
688665539 150084371
154620491 656157420
914193148 59181963
626670845 767179278
114520468 525666156
940843171 162823966
355765931 784133007
428237052 91313998
141943936 18523520
861475120 523113049
545367528 43032139
805627616 875424327
678396637 149838526
414963748 491210981
780944717 669151733
545194819 322126609
819236104 552331664
978284029 585945606
611513627 457471228
205641237 578550449
983137384 146484407
741374415 338903314
783133768 22127821
282733666 925077704
40651341 144208785
448190753 586018870
39757278 106334722
461443196 718153915
256173248 876406945
61881249 37117965
398075031 607076068
211760928 69827488
11924085 190044957
508289448 623437712
647516185 713930685
54504514 483169922
712931447 648395284
822073236 496065214
670523105 104806902
273659272 711174446
101532041 721850025
297193315 141289320
828184747 611152866
711959589 84357995
340076164 773840839
973992315 738151195
233433260 38269596
660495037 245357346
228314553 168784485
721311412 728347092
882715170 775815927
211517013 448162970
276727564 886106604
944228185 947250669
843429860 70403810
658425114 944961901
792253835 808134784
938767575 472954935
419287649 503243518
409829284 759363813
129600710 236337952
350031361 215550324
274607549 10526397
460907670 355438456
31827236 34735436
83785548 767058761
810551363 147818915
215221730 87278926
33925518 11966268
887045949 877355378
82370078 397987416
674833633 727140267
206122199 466117561
52611556 477926202
821877433 462440840
89806368 951478143
551295147 439837729
19544821 825902696
302880481 480452491
33857505 187224071
515187927 117643053
954282832 178255643
265461969 22020916
118050923 151903841
33987184 5096871
29259219 116357263
255600642 556609206
696013884 461722841
875243121 748625440
939649044 697120554
63582634 29455411
501115050 614877781
321809495 520659871
293296830 477206330
853628717 327154335
664430401 221332997
444797389 618713233
399588641 562775712
640734149 370155918
714679553 527237687
227769144 596455126
496111304 483369786
5580685 192125188
945092627 880823807
940750628 737258024
430460714 4333261
619229790 931575764
471727396 793555639
304751989 765024226
270761968 10897059
92178561 935192369
232230056 389492304
406421955 631818697
952268016 899672458
1974615 666947568
426910145 82260113
115919048 923021449
565629899 121499733
967662991 363238879
2323539 760929973
100496903 432784253
617779588 572243047
216876371 89506984
218315039 374144714
854531210 489077007
385041773 799226125
276785729 617271829
188718428 535724039
101606880 140986443
435396496 103581495
660450366 714822995
38357962 776369414
490360798 603987861
897869147 458023788
967226740 752709041
71470114 920239997
38009647 689249703
344999397 254886018
778756687 563314436
629030732 485804250
52391442 14072504
137546729 181693526
483860688 326265157
717417565 585467568
319767955 5330414
541565417 832734675
720153410 579923379
461620442 63030561
183911239 212005942
521054349 3654332
964714983 592524464
923894330 2724630
134290520 268893726
110127002 913047207
832208163 739157735
251367810 737115959
605746593 388914539
771325839 89607280
567696051 341259757
527591202 887464006
346590172 69156618
572715034 919259936
649079997 34335475
982290497 685507590
246341417 355861199
689161923 63572754
948385663 613056252
66297384 82676182
734466332 176424386
848239743 419190848
768098475 952123908
8823161 226361422
193554800 780149000
168485056 761250851
121408757 696076259
501231210 320515283
765232877 73946243
239775218 266829228
108281718 74582068
952336818 207139490
430443267 494015094
270712244 231345284
107071345 189525982
166537820 694054032
365950368 14777563
113244879 134048843
819417825 122068040
212926619 12972624
902217041 381411675
774223476 876142152
77487933 127971039
196657434 695237165
201917283 288949006
962066393 162715355
363531074 766919564
222371199 793974341
113451012 493083443
25319624 73038711
682609425 191857445
767092743 901076148
59151362 880337623
887641345 878569187
854922017 100567963
744058165 609655411
481979638 370797994
485797562 411983926
498769034 534971350
107221090 700686317
823920356 921803837
715918026 187451429
541239754 938289226
981425771 654690766
283889022 859261749
727729478 966498448
51119193 494822220
720090949 962786910
227676196 607732293
693872450 82598213
560816610 437930615
544769978 42796247
808728609 30567540
307296527 160013996
418055244 414517617
860700313 241975600
188837807 429134693
281943383 730077562
367423918 115885507
384768327 651312940
975147257 112497804
470327741 878782804
459836379 42935043
841569714 540028929
650667336 387958517
475143496 64000299
825889132 19913474
106796547 487134095
902997369 266609428
647148091 321052612
681127046 360364758
415544566 869964853
789499451 697487950
452558768 9439722
813373457 837327096
513269016 788520713
802341254 983596758
519819871 114693986
26531800 213905938
654722916 529715491
601864455 129866411
593715790 280269941
2296239 553028691
767404036 905293608
819638120 267068480
78862574 353281519
479949592 494407140
75762725 121965396
44411443 528321494
131405118 857784901
218164943 644674135
498821967 873022551
480787246 18641837
987716538 359835400
232547775 494955807
742067245 834412231
477338572 188299389
114682171 332151166
741328080 734602561
89961127 413482553
854187395 168823701
619280426 334136987
515747196 695043152
456102383 560158639
75880999 440023856
417943539 146562296
84697990 916765507
19584846 418001590
787923698 859817738
630353344 20471473
207289898 372420589
707400058 684628471
560719978 674598583
16779636 154564411
261717497 106740763
420563319 115904891
128080819 39843744
302558232 643828015
587403250 611176970
56503007 663284249
51200825 474446547
809846545 988415170
243728407 681947746
258933113 31652104
541765483 889286457
904639932 749055382
114223399 464556343
286200206 674943377
991671280 155496196
682024143 105905130
114753313 102587461
74326376 95350486
142431205 376884608
739178501 582350810
988061578 795681509
98151412 891778757
122644409 907997958
880193926 218889170
442462057 139127038
103057628 984227540
880929850 7697560
585799275 995153249
324770257 724515835
522612980 168957891
880012031 204637122
274863021 847281699
159740937 349189397
942632185 154688496
726074006 534327040
737039306 566651937
182524902 835190719
310947048 305169311
595705030 43657327
524058481 38167086
35300720 627116109
874910980 916230570
487330023 313226609
911383818 664616635
37742443 286513151
833574526 770270829
491150273 108437546
617552527 650891210
457626944 412701065
805579707 36217303
947028105 395135366
455385594 129553006
230326084 766332642
287238671 826031114
809989970 811297152
716714554 845290690
290929615 591625534
761521259 630775992
904852143 525421430
295392626 795110940
811934582 128967151
565381768 155601208
89921052 35450648
659008773 400064350
448151714 317104833
436281653 247696172
712240199 891667247
377249179 942566284
510516243 664487850
621113751 320506212
328301356 190344659
18313255 471747325
781970193 779834514
102523316 539338689
157772297 250432297
186965982 822223233
231915802 752347751
977824442 321836854
640314753 489349568
721901204 88466466
806454401 10699210
188678993 518694599
754882812 565928172
313777236 265399054
82932375 787407342
438421620 263750085
977752001 456734875
735497410 612238547
89085742 838020727
4093589 246858039
88453023 191059571
69081272 172885179
943407322 899422068
494722034 436238429
241287989 69139591
377221249 47742389
79838802 565900242
418953342 687237968
131828413 732730579
952637022 67277143
372654274 243574995
331027228 350406274
700309870 66524638
962644821 789395612
757061719 966738410
36253650 698031096
10314334 957851277
870916275 953721657
709789698 218154662
242476439 951077687
139810608 619697688
851336430 72165764
185597930 270289772
759403732 169942697
855536705 564557107
89736194 228190978
808132102 420763423
431113606 508441971
339804415 246274780
150353936 949382488
65529543 39123940
499929937 75843877
996975218 223362565
29565533 559281269
441517228 124558326
362875310 581327836
744256015 66728093
653493600 929853945
337017865 265413685
952312996 45070923
829970792 42049190
273261901 638102893
315328967 704375507
999061218 655133382
950650287 149415153
457032223 16179829
188539093 956962160
92023707 38030664
180324724 974105595
449828288 474358306
98663921 812703598
55686141 695436290
879431691 561696095
477806588 68965910
827109780 430119583
114036833 509596925
324685127 239815089
216171 640014094
944190596 999277389
147663829 747357237
1208895 604696052
616053420 189747989
561658211 560593481
80295007 594499290
387215430 530123295
68857595 338395705
195343246 977060092
33831994 74774937
391272540 364154936
996257202 70898674
794274519 110294034
580495599 118959646
202625477 580711771
611490094 146816073
579989159 759153924
746689664 581198055
363849975 215259437
623462398 778024541
628369273 703757405
372523830 15584702
233880700 293897779
206496761 429223946
270957870 92845109
356515237 662230411
457000045 205288792
733129085 103790917
168099181 166141037
75266917 370724658
746852808 686757012
370057085 179358321
298427289 116746748
760556376 662277264
184522540 236535127
292818158 812891813
940292532 665341988
680992869 26689585
959239768 740005984
455913532 82713991
832851093 664945123
597460756 142367491
870233916 183106194
98674762 38333096
349247232 173941680
409057754 96100039
713215046 779114840
275458360 11642334
748377942 888531090
526435952 785416836
125066216 819254111
450825002 65358748
337112452 131817870
92048333 148868573
724340208 400478219
231582565 409707654
65423342 829043321
552075145 788173612
12149515 650749908
826506708 213913101
677207942 88080815
310013140 390422987
719712009 437987855
254581675 320606305
326518944 781017627
106023140 304101515
600271737 556848143
221976617 937384190
541182367 166541304
86252762 118038929
567019524 170351681
527746583 484959220
851911357 79821728
125649185 716577226
583087990 952155893
930490327 112812285
892753062 93019820
503235272 612465071
531007675 757816947
933071376 857526620
391350927 891610870
14144488 991622665
300975366 236121105
781523208 842157734
402662409 720292324
960196663 969681933
743160360 340459599
307157506 595071716
272797681 432806691
164165295 855885671
237478937 94655621
968697956 130231999
187675441 324449581
595213424 718683117
934782882 380801153
428726090 326133809
124928376 442870578
170272827 425903743
678991683 804312389
120577830 81654091
377121066 80774492
903852379 120281425
273750445 63526238
567869495 546548127
348849284 732034790
254950151 586328221
826690411 76164461
569076574 866882207
400614042 16806351
438081677 187913278
250123858 866807767
514047087 375052235
162194698 536836268
800955978 693702735
341148656 921533808
627873180 718269722
854824654 384241912
691067502 128575098
447768151 258936996
675123225 796617435
990971787 930073377
235462009 670178551
6237837 657054938
389577111 259368233
673861289 827658788
447281511 923985148
546982908 813844952
151553736 709177606
350681219 952509714
255396694 544346229
874043521 883269875
115132305 581384528
267511786 806199807
709959626 567796291
65136802 237599205
216930079 908624943
20188935 452392089
431319848 878943127
109447026 820896959
138311359 635824669
501072101 438109225
412326170 48055008
104470530 563879906
609748969 455151750
368905973 865145663
999497979 95465847
748415537 114630283
676850375 868443678
773346444 239326355
436239968 690999601
476925560 653170048
452140897 349630849
958078491 883460745
228573975 920041871
556874058 219401688
408382893 57946158
510027267 820709064
958517521 614497798
237105323 568266489
69649547 606011297
285928506 921663880
701477144 34344042
888810518 230843873
755304074 514673315
470170228 44060396
205672915 947095788
697230444 657813813
149242990 507825288
393790911 377816965
427867158 803181323
449735007 836250051
713643835 959762275
509475468 672161356
574260072 599097146
92944198 496425973
57624796 378872704
270606206 759101940
265733101 11933077
989945813 21037174
526606393 312632394
65097570 584795662
112244535 614844368
95125828 261487525
122669655 488916740
639304490 403053167
144614416 89039497
91819572 858258252
901318126 453811394
382935961 328094551
52908539 475880159
824520524 110533335
707269218 947643084
722151630 973002319
959576162 564613796
846555847 338698908
877246191 764169772
923494570 989490726
231530493 18620398
250978251 206716503
360053492 742799095
462286024 504667908
684354946 554105596
215442513 585673071
7916990 598378474
913767622 913341884
74258633 590804499
23875219 634044205
390963937 598543203
459562877 203056452
163156998 158635077
541755360 40403188
922804849 317766283
882410269 6851696
188903035 133388519
66084553 401472881
728703968 528370577
906140790 413058914
82476173 121583302
851248339 942909518
572478131 617532315
708767755 499253118
60853167 585159328
133297322 451817104
183702530 592860199
654873556 199375883
751495276 49145269
92295425 526816479
366911553 974705694
386184529 408330942
960610567 452269082
809803824 689314535
980639659 568460967
954889803 915632186
542560623 806138141
711058057 115038753
276186809 419825812
614291871 337039977
4985139 600105547
788857081 41204024
45482099 443730637
240579907 796977376
492875906 332875332
176310208 712303813
160097380 562494737
120634755 120707946
14763818 930438579
662538835 847919831
351415899 617428637
763552017 893976522
276083132 327126427
9015275 552269941
746952239 475823500
889309918 604453733
75929047 530683353
498174111 121411146
974413990 738754018
770904876 319806249
924145704 799731438
32110062 84243083
214742528 5261171
57467384 82022700
788216104 720006219
929942532 139632002
189951210 546010902
33608523 466034342
873137329 895140153
870820637 472605922
223480007 612646909
77059654 151925408
143330261 427750119
125852908 970260605
19020490 749274139
142583207 943166194
549005576 27209623
27409277 763748105
32470794 84876661
845770805 820686898
657399234 628229690
812835254 847350444
174240591 698960132
165901139 47377920
446616638 36721776
372500196 670096645
649368685 302076204
674538407 645215300
729826323 800391316
615475904 748846813
402181808 758059111
692013006 951187384
785268735 571938637
567451842 670255883
509331652 265739001
343459135 19247240
893968691 156294388
866597684 920725637
855254520 32498823
820619911 154387512
69220599 193120106
824484157 571105638
495196310 351538918
68837291 77538986
4446587 684313195
826385799 406628395
294888659 370915158
210332132 932673748
942853796 777783975
602929631 304701801
896039330 946388766
323949041 642524374
955199508 43063079
563250010 662970382
75561902 236386274
817357894 997298856
429506380 494358404
420920847 777219044
845897322 489758138
854758030 850343909
26587686 681143828
256972303 321476345
52058986 467304436
106666447 847429136
97604764 709596078
4647290 993644094
508501197 181112686
488684821 316217058
224175765 51934831
979187440 299737667
140837459 796545333
149552876 570343840
143420091 570473723
200079237 989317413
60231860 54837267
839661322 86819546
588497449 949149979
260812245 493072789
268970768 367478692
193018278 366575532
77074769 197665569
212735979 438092320
378778255 701420801
754309379 602954020
605871986 586013172
755208041 746709445
235074859 904760917
169569638 378494950
475234639 369648876
367812362 387982853
277002497 59990037
474802399 865499946
9140016 735614644
358572735 130627138
103093336 551591013
497202671 32684459
601772936 562455004
323293134 980551191
116392158 930118867
436021564 722264144
516132038 43745958
321489943 751206897
948506875 343575935
129701846 276257867
713224811 350030563
664240720 990227308
262536954 139043118
708243608 124193324
727174117 66816342
254820463 682783807
470923709 752023134
567984620 72696645
166994491 743794108
905764190 283386650
673912974 194302108
5650793 42561366
238048066 179657090
646284617 39071295
523233026 628502818
315329162 88974190
978533381 979569883
931717853 93586688
971129355 639961460
217780013 550819825
559294156 472600476
86119985 882734219
77139963 654104606
807947218 244134454
250415067 566227762
527521104 924328042
760529870 385688252
819405762 851094290
565345342 465690378
890165585 941094722
94193195 205494747
30068912 925242930
37580983 814303119
18829618 8710337
306780932 89125985
559530163 866075088
561726461 645650148
601325660 638866424
152271107 409272878
883000878 402686175
975500640 410521982
179530570 588546863
796210234 998936332
292157506 214071929
317143063 182323091
7683005 263852613
240334192 37751917
41611896 277915175
704571390 912957869
286625512 11352321
2083853 698672029
729943763 563810314
196838531 331269422
55193091 349109638
593058654 938193970
604312167 421075647
201232305 783842737
9622509 997442539
635295422 154296370
64030821 804954840
336619461 71713826
68807452 576953653
961982098 962935703
854868828 666553487
875893572 994010694
530422162 730493779
692682723 260365924
146820447 889521254
444151701 202013538
91147245 37210354
140207507 695459413
458286002 341439812
331818503 320424865
191398704 819630280
474721235 107945880
624585119 663857050
179659706 545908925
93327056 141641804
361360981 948195884
660711645 89770906
794722932 43650161
820264686 339922008
304016085 967085133
81959615 748167786
169098670 173106860
637894495 161822532
721082627 96180496
503262344 52901130
269121715 547177403
725047764 596359305
655123283 202149236
260216354 834782989
748058161 353543411
828941147 109419141
154255648 342169146
51706402 948978580
385819307 871971088
141416941 542351746
839056220 223376556
143035886 860671244
396483417 780930381
22493775 117566043
729627231 378272474
22983527 998748946
925449877 600547645
447624604 580573159
802696881 707840959
267872501 403271395
913900724 949330003
365206891 68156371
144015502 416913293
869651306 529834809
288884380 11068246
72186554 980456954
86961157 67738794
841128197 483444574
848669175 716138327
453526971 578296405
94410800 329026853
429561705 19860676
929574498 877186309
452950189 584787733
437543621 573339044
988059128 203960698
522669046 353266018
124633424 666684548
770179311 994284730
49035710 911580045
857869330 973738620
892036998 944830487
41477413 585681549
280791414 890146589
154336229 586834740
320959347 248747029
915861593 603037406
121124059 697952444
332740069 426590602
135256530 770283690
999929646 123315658
974244389 375115046
329098030 98877812
41799593 99277341
945678896 943351659
863373740 656064579
917090278 607927092
453411420 811084045
46124994 586719188
553746987 200461223
173553927 874706335
449208252 941931874
330260094 422848665
492400672 663000163
849439267 627657202
285800207 849368912
750972860 112560949
77000311 80070890
63955115 118799905
31864585 9634010
914667918 747754679
518214943 684274549
355681770 824142717
495358593 401806764
410861905 49105580
602267987 436932186
776328269 903992593
378864060 106588362
326841257 871264732
622104880 28796877
351438287 907905087
878165790 102411147
20466035 955166101
34998391 84421150
926482360 919379331
946571515 693666631
519650363 317302811
377941179 875332134
141445528 725816127
129655251 404823787
627438061 584439593
841755973 256282683
488432185 73136386