1000
998911939 14469580
801910454 835524235
924052809 151599226
906225034 728418914
509755094 338138712
966008411 168752595
557095686 666868004
107969074 93808901
275719945 506770802
612842276 882024794
765352570 972945892
233370818 776185470
195727016 269996082
484393028 372783110
998495516 456849703
31002414 849923808
471319284 832912868
537964397 247888446
837028448 296705784
976307361 346783542
634844496 794832125
515536137 191940182
461700128 623505212
285749083 589936427
130276013 751107713
324477574 748144937
724053604 557848393
376846760 919780620
827844475 713756142
145080084 678856345
23122199 176082498
381296506 494441483
8995365 919260903
594846283 698540167
215966686 423669997
45323708 850811183
218502122 413376200
895267719 532718604
889397766 33533155
122655031 872190133
784640868 447132605
472851423 361210826
4980997 849698183
133507799 685341827
415970678 278587883
364198171 439092877
454670381 745494677
933534360 316182100
517271934 380896997
14722267 733238620
804566994 912562330
436566156 23069115
178454883 184350228
408304074 67852648
217883383 530959105
940042781 2524251
830608064 265410557
363735077 688105416
115108739 497242876
373447242 383595772
775830760 590161767
822688649 83017494
188172797 608739363
399199595 705444731
989636360 413921862
291199705 794203353
179000545 727765861
669788823 357455429
912116090 78092896
425308077 129999472
461568355 217867212
985040078 144692772
483277769 201291508
832798188 450902863
698534385 58761783
834498635 326881498
648923550 509703637
409898992 837096348
118442999 809098587
542541078 108079358
75536802 833740783
754799066 254537348
414022998 277104242
611992777 178655441
207713492 889817208
161171267 521798201
107684419 146211345
666490973 443478543
200019207 499289161
746897760 898553592
558050944 433912748
77951443 59490848
943616385 340366790
896587196 62059384
1981730 291644627
22655096 77518533
125385410 629970516
184572235 391924762
759591112 796565012
423096557 967304604
538898573 584267824
341619158 499099347
582995523 8110131
942577890 783014731
359915646 541992003
534084676 917966590
975904751 464552474
977457438 919521135
804919264 726560987
834096873 806900994
18205614 709268324
884419527 996107379
191755193 68991761
240548494 951346306
718073127 663645051
771167263 109488054
100429228 112786421
608587401 683424752
973412907 403681644
318955836 333328552
945673647 705556866
103811495 921578397
170109339 933785288
693615885 975028603
660346274 380229112
634445951 531068242
942013790 371381831
527175620 133768982
292889947 767724114
937631642 10963073
283885518 561315259
120451127 384314747
526618034 581554882
67739498 352547294
985236526 239211688
685875846 930910172
944768554 642203695
705004922 967394248
575988982 251137161
794939204 88851610
483882627 429385154
619919852 425896416
800766986 999611827
412181752 93656932
619852294 202329748
957136360 903737813
616161361 930103842
288052559 142779394
364175077 208308411
347843042 349411603
300036453 33718887
132838128 97321360
528438936 690359405
64715607 104427918
941496566 859654812
45795882 277895546
141556319 518232088
703791962 794839659
517843914 968490068
741012945 137696208
23336169 550665659
893950375 639497530
333285854 34519287
634793278 697460931
242827698 982636320
46872533 542864151
868871561 32227016
640185511 397310497
722586421 557417473
354254769 516599340
269588638 252567005
794494886 411144957
770799093 350803201
58500970 141159361
171809622 799513915
131371923 195145792
350179573 25322297
834643322 683465427
59841584 469436600
233442712 155185636
304589273 132831599
698049787 173460834
165058615 190751651
423287685 740161390
748169124 777542454
109277083 17757761
30109458 903771969
281419073 653424905
107091523 339920043
794584266 278901146
139433957 925956189
474046938 342129885
951278486 161206613
878111666 863636424
630643213 111554377
18822059 935232487
244385977 569388200
961209675 261960946
760139852 384497359
2122336 360825329
14556166 111399419
231099445 897181979
867687743 365034872
550606883 974779266
704954915 197707503
106196765 696905226
123663691 432760057
891551465 927458532
593966671 769663131
791094955 77126237
733733862 662433369
12358723 978119839
231821568 826084752
92597139 844477774
63098464 94719475
57819457 77654630
58635248 288918902
974836609 926322991
653953774 377959846
753618611 211425042
575667349 859815376
760846622 551847394
145091787 652398087
479305925 739058458
274577571 122917234
816184695 8311432
785350603 681059773
838947626 869688525
507144524 931544765
714166299 570242989
878780594 771985756
500413973 937415842
913421012 327766936
863738833 419891139
705726782 469873797
631316181 133910484
182205526 244679156
685757878 327297313
897077243 17580157
66355770 24171167
140497391 882540466
884998955 778364348
416116592 576462934
500569226 923261116
360524052 67251878
346020458 239304645
839237634 846434432
29236840 605174999
26717721 892975673
25066137 732444503
215365823 508898672
718871341 397571350
753577829 257145572
724868663 503171425
274725729 791224434
527342593 267739474
526281253 264857901
898620176 942397845
841320835 399189402
718175314 201844886
466441280 916712127
293665885 158195268
615662912 322902725
763370267 642380633
68394752 640952759
227341489 283760575
149851430 946212830
681331925 903429259
203358401 406200588
259117038 330600485
49941375 786459631
598339959 428738982
51317531 349476489
223653180 745154720
748665891 941828494
946999606 67623524
711056974 93181844
78335146 326719885
416084569 841705414
969100518 484479321
335174526 48958360
768239897 485025956
995171190 449571821
240971569 51045945
708288763 500088607
381646430 758230138
139064591 979986389
39485473 42898476
181979231 263138653
788053196 930645122
57483501 587569155
850785001 768540475
680750999 929120147
95260360 96835567
623341914 916877232
433831243 958516440
965835593 202071139
296058750 813523136
504159314 537030319
864569081 212448077
889635280 246215510
823194569 28699870
78718253 862680043
924114701 260697484
125818695 564684250
43858960 183302196
4769758 894643961
951842672 685520757
676280461 899619386
634872678 299622375
669012971 68703920
110655168 487364917
123291413 406713918
153404407 627450728
943744237 17973487
692415159 685895870
116705352 515609727
567112094 195423605
230806123 491226794
308637443 356624819
55911043 352496403
392443369 60680801
99656717 196802394
598717912 775937179
96421779 86106944
928075908 617951105
7327218 38731075
957832376 130618632
445444994 111236782
610585714 241705584
129210270 155517226
927601455 98431976
671126953 347229902
293855581 901933077
838456697 602493024
111074249 746884094
807505782 503517618
660081250 907162499
700320013 111315515
535616031 649258146
49938813 316208292
119725604 57266032
354939368 77557980
40401018 652900716
41311116 503503086
894606300 23037740
659020312 674724108
121469716 182663618
21954010 267841651
84596694 712927061
870334676 48187297
312327508 530356811
404221270 824925112
290035663 104541282
936240628 825651695
606315782 986179441
141859986 578557741
895961827 349315708
508632075 936362845
2216423 549943191
292382284 749339078
425497286 951402596
276579539 546967002
134066214 151049903
814808654 71179262
716493318 537659683
119366560 28820826
68016493 376104184
706262292 210568510
333161820 495019273
36220204 939477602
333715068 30596545
370551696 229676894
232428607 879183771
18556093 87161385
281643316 310938377
689016817 707140602
114857327 965596356
106623957 248923541
969162614 921432611
172619157 685655931
311608647 144502071
566993111 232141494
520606255 125771757
442710005 853768075
620791030 331446563
645762031 954506098
214559462 16313726
36699346 299504424
895497498 55255439
386665809 29657167
218710170 75682625
736797769 333567497
893795335 843421726
582491038 715474302
617370691 755110196
253646587 928979338
899612267 820639698
13637186 272734876
946411455 308863545
126502950 419718839
640310108 772264981
374224936 707385925
641095062 410924282
6890348 389108913
318696075 246072511
418766080 537406246
174271490 155563848
870973743 68066824
998985574 305981135
636057481 468872618
61091330 889704068
250368310 813219951
562860119 264005496
85954826 361787928
572869041 64974131
781506767 65695502
689755466 8248056
773081427 330850527
419172339 632488129
719959440 737868414
878560640 138725519
127791013 52832129
146805721 998764757
973415309 998307650
304745891 609472789
467180267 218353575
351693210 717548577
884089880 914553329
834070427 822561061
276341256 259455821
887535192 57848022
325151324 429807011
66096079 950749105
760657539 337784772
583237234 333133332
928169540 314314227
324375206 55960553
367146357 323697281
54725309 193078019
322004930 211987554
802550808 641701552
282857483 6760371
211766482 166947362
921313700 45836909
989508423 50171310
305292730 729559968
108019332 482960408
11883333 26631765
433709513 772540872
216932891 869463101
958190558 145102431
183777327 135082117
53579338 403440038
458779399 960821002
596518057 780784329
25324909 251585218
275002234 308182392
258345589 486768717
475129754 179659289
532605626 317154531
229830599 690414710
899230853 190366285
173375118 911114186
69514405 459600985
536171411 138963650
329064085 494361969
136582435 365357766
629444086 190161773
768797805 88223484
3499128 365315861
721524168 28824037
616901080 996526402
337006429 875246669
335811472 812136184
907422312 868417098
981807069 137252910
411348162 881037921
180135550 584723280
644668461 102166309
44324264 180839871
241129959 225904703
527718194 377712395
591262469 9678634
567874168 212576627
97902118 571373297
577892489 671942640
600197334 47309922
520985396 937203764
775072945 856796868
601856301 682495257
577730320 436179723
672264521 989078482
169733997 704916425
426318115 814402458
807082734 323158733
995242330 48212693
401579790 375476877
425925088 992842259
385155511 846315610
57935240 335573984
270205260 635827729
7516623 870402595
535654005 381018373
660122712 310726949
90331595 114495366
845738560 520578269
550675089 370519435
362173104 720409086
75435859 788491219
387327898 882518594
964166306 235086581
783247641 365746095
610563458 61689082
211104707 995718970
908004692 269039947
331292953 178209952
757384030 191325930
901128901 293038034
424860658 413767966
456281338 515192253
528263332 302019897
35770521 931454775
672539332 250459979
504380214 600491546
38951197 891708112
335526493 855633857
126794692 118774133
73896305 737358151
180463215 285001012
585593474 88467906
406557314 916886427
119194212 163941343
960728711 20323112
309495732 385589368
286607432 765777070
753297975 814870764
67796966 641584850
598841892 592852653
892044829 103222106
45860552 783512380
994930218 381387045
639146236 974241265
500161178 713042541
564115769 533140747
850559908 149709242
474125007 257117221
919112023 593319220
273574918 879840733
466158686 583070650
117946455 752766119
348847719 871244430
420153236 269161040
365345634 18995128
714530047 257390462
974733589 760390599
40902842 822180160
141777643 532565432
796421424 494455175
98124327 213053546
27595921 948684235
362762788 501720928
58317809 134391164
947556502 331892727
14231897 266231542
914963378 984694707
18997660 116327450
708455490 291667250
238004844 73801123
163178732 952534891
183707940 137912320
712925489 77127136
812608835 707219486
609692568 461546612
201674660 560333249
674600159 81786935
361533837 37362946
583507864 419851646
24270465 383580719
604260728 38502362
649812261 371740459
875713423 521326275
488067909 584168912
812993526 726072754
510486390 828688612
531123998 694194330
819117287 96565841
771321466 631726121
803785327 233530387
93272732 5459987
793863637 620389245
87246922 155397473
510268546 523271140
427765474 534539011
906851860 32026201
425557727 409180474
403766660 301271149
930506750 744350923
737956415 596016629
322940030 248442804
424705240 854064029
942637134 96338880
950629870 566474953
728065001 754415196
800005341 673854088
612391537 593868977
146759686 552154814
601782804 657028232
927942308 29548277
191567242 687310521
61574478 617124969
96490995 317857492
770912472 26997744
62208415 508868887
475530727 237664799
609828045 900235967
91728827 404981533
996574848 42358696
971456486 577156202
649290247 771461826
103526643 114198137
217847156 250286330
518869305 819629961
907314562 446811613
701694592 951398159
134122133 615785425
421039481 83129482
933642917 191951953
962643581 848367686
553337194 438174307
86032485 163165238
190926628 30277666
568146771 40017829
925152718 392119611
469690385 426959318
16097790 573217029
541157455 233944947
676019713 60026760
906091262 435850628
359354727 607785853
387248786 345993214
76087631 808288268
281639051 9730548
852756575 244282631
710614588 406093768
534973293 649163427
421775360 725899921
531957448 989922132
618434104 457110165
234558096 88124488
884069483 250655886
513857871 277743291
484600833 189877583
190286405 243208448
625728212 402157486
850994302 865493352
748150701 927081933
526297973 29789751
789328835 379054547
126588736 352459777
637664669 661562029
854139558 59440029
239978303 386097005
901878515 858412407
695723524 136436610
799053250 432309360
387092496 312911120
710052652 724209684
355305058 752855411
967418132 981033270
155012897 670928787
699042975 755679952
450527074 225340948
637986057 92372262
456911849 764574793
444832039 94576518
278653176 151487951
6532901 371147833
537584956 908411416
82076594 85824834
44848025 881129844
518134194 284456875
46557317 80703199
8666558 401862375
833558611 828601045
235411998 988571508
499529831 934454974
596767813 950056905
12312275 234753869
42429167 469224124
851845016 339777560
563800642 130498191
491265511 570333543
354162379 881366822
331261312 436238973
967191656 228625691
317368816 485325849
513082567 363926133
566029049 374265479
765788509 252104013
55382877 1200506
93191874 554912709
788171834 689959687
357485967 800484109
924713556 252431488
269708233 629074925
444725403 686025229
612089471 935990914
108875126 966251850
669874089 440136438
402490822 637065744
668762130 572375992
974907948 34361050
936302125 393453350
408626529 554606987
645557363 464009407
408323848 738749237
871438470 49012035
428708923 81440790
849496145 205938832
333872279 119204377
835013757 778597682
657745960 299619581
567104949 766621086
265871430 89495392
206757524 520878606
726561136 875519654
93254597 553985437
909880704 882073077
947438787 171023586
289196417 592996149
487549347 697520265
184261739 358987816
746532301 612970662
440428607 448544799
671425848 626817240
420265530 358955959
257931275 78011489
658575540 825036224
844632576 924446971
914531616 903906454
297841930 493609106
631942461 391096528
47594542 394339518
125685958 847549684
565363104 414882375
293062186 52912451
112402640 477323926
264416621 711451295
90294587 557361582
12512447 614236790
184178821 432777977
973192749 442110096
510789466 631768288
119662674 207938395
408731612 886710644
111844848 706573543
232836103 596303663
950186425 132947000
990643181 75872382
980496684 408522639
490754757 273558869
313951444 455673751
750882795 578368065
19641399 693693737
135729647 32153846
160446880 172424822
464931823 133639628
467051273 828237644
617924270 586713947
36176038 26655882
325940944 537241
585745779 558777048
449357258 388448557
691724048 440000439
464320939 672220731
848523078 807592050
798295954 14990875
115782155 401695103
593358940 135423554
95388839 581604941
20093755 108352073
606546118 485025578
241991701 73597390
165779575 859915971
512827691 54471968
739088207 838768635
55009209 177350339
397545682 356882821
565798896 89269729
796883260 882636189
614006814 497922691
690228239 264819122
512913566 806010394
666514225 958788861
793950302 614419418
392910155 814044057
722771491 999456273
151585989 964763192
73053662 317365564
677195516 438397707
371837532 268800077
277166342 279363095
298666770 527228378
636245917 864465667
469014462 285645530
599618209 83021275
783568222 142362801
200356751 148998141
948373195 866870976
107787001 594839851
481290393 353213511
408883907 56578237
352669783 560469896
21341428 278239800
877835461 551053299
716637507 102189346
672369730 846320203
381552442 971036500
373548581 17798358
688018520 842563043
303443888 287636729
778100672 939528464
429999530 978457424
88526605 230889079
697844753 48829960
825728930 31651500
254559825 87129190
88229737 607229609
500115441 109571166
737985763 230467255
513140819 307139623
332656601 38026902
153459826 714209043
9063401 379524761
732007401 697081922
74604157 887967644
837235005 852704829
827496107 119750888
683678606 768539066
350639967 234039713
669885381 28885250
265691213 924445206
116014441 353920950
384191168 468646236
316008470 122176930
699113491 829149289
281832908 31770091
867176191 435292734
745979135 728755947
814817495 330502889
278354222 889421652
70986886 115589226
594642834 898482994
235340114 130837794
519538413 438496436
364877507 41940147
467381686 630568720
818901708 435912481
984489670 55609229
904558717 153014494
30302514 456188561
982163783 312135422
487958653 701856328
747428156 86454141
283128628 414762004
269473384 561482850
156700009 340460271
677072076 603859197
91459618 764928544
734696991 610998031
203424979 952090852
505454533 523323020
435175925 324356240
959235501 272181949
379965469 716310572
425196443 410267983
25015486 259876579
722403405 512974139
961732907 322347914
451944634 97377888
589626272 721418019
658860738 746326281
61878289 188449167
202701832 153337907
953377712 937398823
616852292 9319044
742006029 122306824
532642064 177181953
299179418 344393919
449363902 679144888
60704490 874560345
941929225 85719976
134436924 516848984
451210470 948686185
839196898 903155104
46064073 281339524
477089476 557441165
27665804 538967765
745890333 82883990
544822026 699268044
20282813 161674318
708587088 614805196
136497496 93745506
791987149 435676915
438139425 93867405
114821802 351360269
820944104 909267381
289596599 807897382
426116364 740807069
609099921 117829616
496478527 507680348
399169140 973568003
65121512 279351298
365052122 811011845
362235289 909874148
362796242 235034456
924064820 923899685
849839652 60562316
17645190 494343154
496239231 455784615
440726913 463577387
807144884 261671017
225361121 96741482
69568398 651477486
690064906 531184673
621823456 39059786
38865020 20992595
865144143 103986533
152860247 82712618
767514732 367611890
992586767 982827329
602646346 769167940
906727013 305002351
829730256 776888557
651861860 178485840
85189525 92588772
494579581 892334409
206776143 719940703
841592245 128860896
223934542 384173504
660045569 845757998
275749644 698910590
719266947 140893787
655413477 872127194
223606405 275444562
92255438 68709525
110788244 694901784
837877466 17515256
852420490 520124075
646920167 504282349
551126270 732109692
449387475 45705850
476960454 656163619
765646553 171069053
785024515 989581095
555242557 445070083
687855446 830992202
996497027 407122392
824402343 504426857
131765940 48008747
779871420 224021378
969234628 890659664
771439516 659628447
760691275 623860005
32268875 260127795
980658708 583395145
992237488 430046183
629100996 469197941
86209801 247263902
640266994 723750670
89361351 48025905
21337106 777216797
731534461 17834133
36855543 555936803
522260990 21137837
456461904 154648763
245159215 278212885
897824782 16598730
937841332 511032410
492975090 970110208
771160205 326150151
553505352 763397692
756196334 35122701
85111987 694922489
134902958 577895335
271189512 224264309
625921240 292526619
853997460 209972054
310360752 890853003
765908857 685138096
911990840 74887115
839786860 9666408
353100000 590127995
878781494 143457686
101160404 224272937
113567893 872320609
550423088 519589599
488234655 159135776
554712301 425862996