1000
881418187 750110566
315493938 282606189
699540817 761508637
293832807 238994173
43805780 899199777
378240797 714801101
591757306 636426101
270660740 616536762
293111888 73575139
218418482 40419281
454009063 89366895
801357031 410044429
602554874 58613219
15938358 361757566
526653061 292074754
138863298 260587601
42185319 306873591
543193790 741726136
68382227 837026597
833236663 112188007
588742728 63993813
679505462 180500033
700419914 950166203
649553150 993531803
876257696 867971632
886467438 330266759
957338527 687824469
740311188 412409754
598954042 756249546
774167320 125607103
48324299 765546973
238711058 943025973
72420563 781904849
537268462 140802790
471447799 370505124
105507151 60190526
434498937 637528968
93206914 134918851
440211524 742760064
980967008 316469219
463248049 867434445
499252332 273102930
407775267 92079873
685512684 859245664
848329419 312196358
837369121 749170072
77743330 76080178
544712398 2680247
710501381 81980859
143483037 34465534
305002337 101506542
94656060 739501275
591551864 40379328
726936480 31763387
635655746 560419841
200748961 98903795
280370639 700001293
224523079 688145907
792081167 762552117
399907924 492926939
74748474 237277044
94613365 5008158
165873576 639325763
7688405 876374958
721306623 3687796
910840492 26308959
105194339 858012906
618326588 549262557
898392235 197779421
581025945 386564334
758199262 781774906
337984483 38569901
334292552 562507562
579232162 126373718
177576033 979140086
619300658 252324507
68933483 713914023
257332666 234807059
205756139 265021071
111182016 927062762
268708868 874538862
805888076 226419561
732551768 276731017
775682118 483460356
327026793 209224416
870024690 85226054
843515676 60525527
976312310 177808228
623033089 408060825
156698300 800609122
239717264 775998958
905449984 161167101
342429334 15299003
395974161 548185474
280320074 359672531
327764589 401545296
86727747 986169019
627964857 819279515
115416390 256163329
155256224 442443183
317904099 877797268
380185591 161419775
938322795 209014255
191744357 413872238
617075080 348442657
66997713 709308699
124441615 972447697
870475800 319387303
987746700 118966314
720089131 120583128
478638846 47853720
522128424 565366593
886539093 2609635
237162461 1955482
258772964 244935039
444398665 576677063
122732306 824584257
590613192 61055101
33598511 782357549
327443693 503189945
130800206 394441406
65014997 107758175
366889103 935490798
279661832 207152156
54457111 999750964
327735284 385612311
900121038 849863709
950978904 786660130
852473344 40657718
641131967 111246307
285592757 85530631
540439724 260841418
762631242 131052916
174412873 648746107
765926819 501856566
4452406 896727025
896297972 69467403
857001554 115703428
4958200 136663386
322855585 911931667
136414349 650590869
297543977 889051741
500454577 101039235
528228224 205444274
141696953 169360190
169206935 279806065
107407176 709646660
540647483 722554772
693215930 715060356
223817233 311659102
69433275 228269639
60902481 965731247
150253396 917904035
81434675 7727951
54567420 404290260
919659618 43498123
54881128 69719948
785066218 407852060
170759183 313294442
613296334 164972491
335170986 782503270
297294910 442578162
344666283 837942393
17649288 890398567
405519102 241466521
202057668 474952377
469736160 262960149
293199977 619989556
33380538 374634652
627717507 87947958
631441266 399893478
983962437 538838749
469613427 621545008
946690809 640372610
934839450 412503496
657861455 122526790
47523119 955156365
565104952 244705756
645615111 582754240
135104322 51134212
824220761 189678345
378602943 146473274
452638494 671802921
618979185 486019032
898953927 99213045
426483345 530395193
499106524 262962135
69233941 968719951
884507143 868441104
461608914 671862947
133460953 119470369
794389737 33500427
74626733 212011042
278206183 572758199
647281637 413310506
476408765 324018751
602988851 855011709
470492026 908143699
379330983 89471210
246679085 130801263
41200609 673162430
661196456 540307133
788640919 582946751
509027083 525664415
303904208 970635998
50043715 289881516
942622721 844433452
323381943 869765808
908960849 601588126
442524006 556242485
14898631 918932772
880261236 470403836
626460834 203269615
231063889 858308171
145257179 477742974
989109434 186457789
3421757 502822244
726764922 792062676
85768994 88308359
317727090 242189557
911460711 367770806
532071073 854083431
64720611 855453016
576365592 973681460
309557495 18889598
382440298 176972481
790338724 115217888
647376317 269315911
171003857 878440206
127624081 316261037
208699533 969249869
355235180 212121290
472072112 82000101
4183965 410357461
22824814 174427410
505063372 934285525
542198216 37134444
640885309 459435181
745103814 69767255
285632995 54661308
88656853 668073293
84150143 731511931
635807535 731526461
853344196 806811393
462483020 833484631
123072429 671182554
802734499 330823963
883303844 127322965
265340418 740004164
390196780 288165233
914431574 895260152
74967111 309146143
784910950 568368775
768581324 382531117
638136030 54214318
289708779 579309237
574803966 373858923
163337521 210611500
105385383 16681716
17422892 420384757
850166347 993011676
944083665 505417199
176351992 679903863
485256518 441692411
419908026 875453298
729857644 186855953
770713449 657341109
496002096 408140752
225709883 264583419
790671869 863845913
171314092 80380648
295671503 746118058
454239571 459009024
956729558 412141308
475690740 826668805
685042419 178373440
672196834 629126084
536306994 848548827
161546300 21563511
142757591 581454326
897016810 872615235
768310279 520246612
382472697 116828728
928387365 608182581
381412147 571575587
324544847 552726239
651956235 620216351
151360650 958712160
79225374 108090208
223369821 407432469
787275367 908412241
438322263 311988554
390054678 974629257
13053734 551600978
996192769 155811325
133055303 745725932
880942914 753881936
118488897 263415611
870710664 899392616
724114546 104639164
470968203 48659392
509881758 975440792
521392097 661242408
934152952 453133826
621848970 10039126
713082649 261640690
918451367 151404911
573629245 308506044
126034168 439199333
860107022 974743291
595010659 845678679
572985576 328469926
452076968 543990827
591885537 175303985
443383443 168516436
132459504 766868000
69692183 642341262
742308791 591084280
303583669 528978096
896734460 925432640
539017223 609817108
39589683 309984943
613738374 613218928
618490988 592288896
52418261 331114363
419548540 499945274
29309396 992534116
828415200 333902718
389041296 272817091
509206704 832424739
441333527 641666208
451809092 511025710
136523823 46634237
954626345 440107492
575612333 851360804
218056485 967145910
313694266 257646169
277130853 927432640
723381451 748138195
372237889 628316066
79252557 791786429
128261339 961078308
636836898 809192894
294981026 25878193
934526339 656704084
710819287 228376219
150886645 162628378
739401930 287410468
209262615 546544628
727517960 637391303
250421785 798090800
604537212 564116051
55736968 734184419
344065044 631634773
482322613 716302933
259950839 414091525
360605715 240728532
227686186 997442613
902437780 522667212
23320806 836964118
31887649 586656447
65340337 182774294
749284825 657258621
470184762 811063795
56319602 50219076
448455097 306741387
848309876 905508663
870857439 756563198
639693082 67438836
388197970 974532049
636258124 500665163
241139927 996863839
741393696 468826114
994306452 496347829
991493326 870143612
185828301 23380975
309316412 103684992
58671623 58601236
760943613 528856386
722181385 817263215
579075462 23152835
124004601 427385337
928661499 847378394
36464888 420870934
767333585 424662858
395402982 403591708
925328022 636542910
252971900 519238071
105369023 99794705
15585899 949378703
969938317 53930554
825276032 131771082
157615546 883947656
42888673 918559159
265320395 765070058
588338727 844395857
788222894 564859683
124297547 716884392
264754430 160762435
137755325 32088014
585425293 385674661
288196076 363269668
874733925 541167977
735024093 832619302
640962682 603126347
634514359 463417353
657056901 312306744
595188435 814672448
48770753 638077108
585747960 314091148
255663520 26603041
158487004 43886413
591462724 282784551
613287159 708733508
443546986 603558838
593337877 881488634
989233499 881533953
97274655 716483778
275218283 832298749
549103079 768697320
435425095 36133791
84631026 92481995
348440536 679819461
759670797 397211289
170412923 345418757
711302438 426076443
372021798 869789442
322479210 816000876
5090347 935766369
524734383 301153687
539325206 118072259
182642320 381075058
852122567 279916976
97558835 979857204
112215724 499178269
748554523 400157173
535312060 833185549
345155522 883752596
365521364 104826319
133480239 388450641
302761430 844782677
814527084 527299582
567088472 137006293
343300457 572178819
925289016 720551194
873332507 317130575
691139808 908491181
698205633 395778728
40924510 648280823
375635931 5656588
999975446 976706809
405813761 387803859
662408711 603485638
124072809 27930074
560828311 257553048
268897069 863589741
102335724 83424152
243405676 669424196
72946799 586706133
94119369 850752169
159773680 819968230
167882743 850913488
728459410 718604731
246692215 769383921
219401907 474844501
775040509 219377352
451551309 33370624
607181211 113960019
636856262 731254020
994406449 50200926
988807068 115819871
913790667 943659146
51760378 9712696
465599696 124707177
596418829 559719065
827975701 756192509
232203648 995858444
459622351 960663058
566979528 706314566
582563332 786381435
33675420 210120195
5758786 485226729
96007173 465456352
451703103 732863435
49226725 298625905
783064361 890550148
414445776 549371381
834209293 466206154
559084077 152325342
443429686 8019259
712044407 123921740
616728122 944248055
119780183 76350472
757427467 539276066
635181393 192507152
325657500 668856813
255143701 183932641
6599896 351150874
501905347 458302999
84014308 551132072
609445258 719595023
294198573 23891033
121482757 128407866
342613542 533083188
133249562 638559582
541102447 845293970
762481322 10346923
642058378 734777859
86697395 252002198
274053924 721878788
297025705 452227779
243251955 552169406
636160420 249851851
903320281 138065766
708154850 839850943
541714192 170116461
411962320 835912766
46523848 533445077
816836986 389137390
66528265 950086548
27696971 460147066
647896871 642694647
470493989 142471603
377472506 409707739
246990155 504042784
131586526 544015860
956270563 227354835
96185266 444947336
477206686 999505547
435529456 37877889
691872843 977243649
207994350 103835162
665672768 254518199
489796594 335026107
643655589 408841213
137629008 523868915
868988279 638042234
19079915 191998622
780513837 396552421
601706361 27503991
900595206 585809241
424036206 709382122
813164077 520221472
154329458 142887116
372243372 589858914
180765006 64116214
419618916 388759356
20467731 937808038
643277555 510264325
125350498 139449498
919105538 262979507
663318413 640610170
901021741 682398328
685125146 534051931
931467104 139347860
414072276 684578663
725157102 838108482
393960784 390837532
210846307 400806596
533724648 435606033
990665511 714489654
352238602 262800780
103249010 372706333
53125172 599042919
735487012 178475670
738492417 507108903
441455177 254327183
235426 194993271
936725512 685360573
581561556 720708969
824708433 995633833
405287631 402381888
686258668 651764769
793219420 749621330
52571365 179460422
185227362 895753230
746466430 537465964
11070363 702231794
762688651 64195535
301274713 498175662
242671206 39767129
5284564 684126383
146610667 5519991
731636009 83336178
543396918 313197564
656561501 368105350
161347750 61849131
770487239 700122773
566130254 416223012
449744102 618701619
448199788 487487818
366971202 194666218
24953782 378041566
896898012 640158787
442237101 50689078
138334449 684908307
942972563 996135368
221551044 89583229
854171713 953187053
25435761 250084984
118900970 681997262
618190335 280248721
596362747 241193927
980371494 15009354
509933293 282631949
633710974 958133082
770119767 682175
5315653 647589903
231240095 902213665
140265044 673477197
805419098 131115847
358385503 748391660
127251214 579936547
690491243 833939282
385639953 715927004
84024265 504540924
250440619 554730954
784789645 699319720
648441235 617677492
714329074 158374528
752825795 200556401
116507609 375461915
53754931 121823262
23051818 284995026
876553281 15833216
958472223 534488732
146949063 169374080
135396745 126716631
749310627 825887988
960655913 134950580
394331345 897196533
492007858 644771964
304443840 129313856
196608037 952885076
746991348 910937112
963775958 352333496
111493512 932799921
727795411 165248443
907139537 603363583
450243470 636209171
619196799 261232046
170697903 766145862
430606126 306094648
892862494 32433107
131982636 706034760
19900041 378830335
455747646 511907899
23602299 760191487
641221755 72726690
565592916 240729456
983663802 381885227
593062952 95157314
314685147 320858362
112922111 74341037
924221946 415681935
710550208 395935098
676913982 881248111
162080960 107520107
39859113 54943453
139953214 24358103
613494567 159853255
403188438 69242213
671761154 279307091
681950054 165499262
352033782 100059323
406228718 188213937
481944550 999291670
135887605 796629697
172666386 248809717
870970734 96888331
664491652 434037295
345339783 193921987
167801760 507420743
301442095 207660873
414880550 293911663
84535330 28375117
453764919 487723768
950133685 978042427
619547214 632083738
143541689 971580996
732143061 549770407
12311286 66603964
401578431 148198892
863233661 574244817
397008609 586720748
523649502 914016615
20758042 868989285
107938602 41076156
228926382 261897051
248737029 643806932
555808714 333272359
524698403 9573632
673512482 327348441
840132414 293059695
959432179 983674103
117157044 544091593
385960863 129468330
610695557 787539294
277667222 326445571
214300464 527192185
765682673 737949966
441208800 638957070
606939251 401663756
680033226 835865633
663560807 928770256
332188918 219369520
114558968 709403676
81459507 788071450
36752116 921591921
933647499 848700650
757782377 50804542
245308596 996259594
32789227 856004154
636315242 162972803
34966078 850615706
690164989 800648752
588565672 131373788
292122175 48021276
385553898 972155401
736403263 49114704
753442010 68592180
121000578 868000979
630512210 202460085
508588782 667264327
976568360 294752635
368481330 586867090
198073531 613789926
583126684 230862758
322310433 71958279
393835562 357276512
922573985 84000550
10441617 363656010
67890692 302563792
411677286 305960944
127235546 596902
355075648 880677557
69189083 476076226
601194889 552217647
531052666 109783670
71998327 507621025
257052659 440479657
94488115 455126191
54269583 530131153
685988949 376580016
602089432 932340865
586372882 377179770
868857769 596814499
740835781 789264815
751894645 5029420
95225758 879130192
5626323 302817760
759807748 74815406
778893987 213518990
479549407 162463006
175819014 551547735
670084031 432871674
992027392 617088500
887997865 46296974
999736007 426503167
275393345 454341792
358844032 861766227
831521563 80218154
311097080 572357343
869482970 62991724
577386763 964708728
794638270 583013086
120042842 406962371
510344846 898936829
620481361 989894254
61399834 796300376
393958342 584000219
229172049 385985733
53605073 117169913
284799062 53341079
396189434 412708761
360199226 755033466
126991341 191720788
835251621 438088421
616594485 557250944
353596500 46497601
374476025 751123
629510688 494518867
407713495 992371888
245972049 28194855
834782495 159888237
824495231 228740836
743888457 906183634
467242924 650009884
875869901 752041986
555867317 272059335
17267100 916066543
879609155 144258441
107787330 567377129
582346863 576898169
124628072 788459717
623395771 499104098
789210840 105422812
993622965 196924334
97794699 92111368
77635544 932577195
251999605 902130775
13834384 995888062
660830763 481077308
498414299 536700663
85635647 54281616
661276352 102902747
970348159 540885507
247161189 930651844
108262635 682024406
360066366 85407062
470484122 983462137
437027514 112211315
88884948 283166832
309135650 39196002
375278200 386771194
971773197 627277806
141418322 838123935
475682221 802249085
171717597 974096521
191466102 257353244
28378136 852742454
212772346 851242649
246144314 459933535
634410846 206923304
141957940 994477213
144846720 464958416
830455703 581874234
577169731 919340652
865041066 738821735
958536654 240319266
125592928 782826204
867597072 119527605
473466492 195795646
774293044 645184089
169892166 965759146
902537334 50786656
671017954 115309679
754545660 769678622
427759568 241472859
976601926 422233862
88466425 121448645
739708632 918922129
555839233 169394716
690779134 420880299
908216452 501832141
513715919 886325734
137174698 233829344
5853338 610641190
429624990 632662737
255825279 599517157
450938236 10878966
502820167 121956189
978705000 257365826
744151166 258980921
498838686 573269445
681214783 587305111
547234445 273439768
358743593 103073677
442834484 49522726
376470330 351050935
551354867 890186249
89893023 688529565
124015592 95746361
151687109 553640583
580925452 407512388
5674093 31863688
270907708 508494260
6336231 249612707
618376441 750487397
508593628 117215126
176273196 42324764
557036591 723507641
315764532 915780185
826581318 758599016
817819265 55568002
962166306 221690486
945754251 52059328
910220051 69769843
322043 61907159
475926780 581247496
321935901 334117227
465627538 592843609
842611487 471963769
694972670 313504281
74967520 56082651
283235761 251240716
98407415 840272353
974748357 266688301
608568891 653846028
25287317 278904509
709414030 839969977
500594995 507684635
892029305 263331400
429970832 744867702
177754913 905897612
178631551 499690815
92531192 644259089
945050778 935142679
116222858 640023448
101163314 43706732
696106099 384399075
147463802 647029869
77187781 122212158
913718170 685756672
628574540 791521841
964661182 190504924
631491817 317772530
698189559 376037475
581103930 128160390
120905177 758858844
886574356 152053082
111066012 979105548
796312172 56116789
766764580 765051384
548656591 867927894
808758116 97279044
104843323 956221918
744308913 182031104
930950430 658027082
867787777 412041323
302065277 684965312
455062601 933557094
2737841 5768513
162110923 436358126
133928903 135532454
195216969 873019613
287585536 306282981
704641514 83897707
214916124 323922448
701465445 763572716
44366695 362739914
860851760 149210018
171478185 605160672
331241123 102428614
115704107 51545253
366986292 417769384
589026919 822048893
203842832 444281114
827817407 218470109
880639240 814262664
354002563 75856208
539798631 494104453
234655543 96956498
430518515 449571668
273395300 131983959
65660737 317761996
494723874 926512497
319488368 666202059
384189522 650729491
621147028 499893629
554791098 840649674
770179368 143818016
515214920 974022200
588099131 195548680
45008662 321254724
9811344 399011225
249627287 402126329
893115678 484282830
351599181 176150546
786370852 624994482
308134506 852031589
942756478 655374734
778544085 114761199
174093146 15249960
765490691 795240174
515143590 172798142
488406201 137839311
316616159 3621121
111861510 757231644
199169801 9386526
78486367 61497499
408397751 328113654
316140182 154029782
664912839 667739364
330180329 451283690
292733845 490831189
155831633 88006676
146205922 934375718
202767875 320299068
949625679 820774920
968055597 317285622
993573063 456461797
455124933 162705575
312599272 419502797
919937219 511769074
428889323 998423586
425782927 689803428
179053594 741923110
843833210 843966433
409662473 26529892
147766476 554912672
517361081 303598109
642919348 516083357
90490181 698203577
836382426 892632214
518978497 656954376
62434189 365067913
113416172 517559122
527773488 278531799
789578273 447710706