1000
483991898 501892083
777360399 190443766
528271572 849071211
834112216 565841714
592931589 509149415
753644285 206647096
9826783 396623755
28062296 990058831
748173938 129924713
273232867 683194813
687960921 540513293
848872595 809401283
823794124 78040716
107323788 295482510
861156562 197944621
578585198 197664813
699836704 208461950
388108579 228108275
57533161 74737148
646466343 502981104
583886563 400110627
709628200 446229700
796734382 590206851
288804885 397424673
572647918 562037752
933135841 113125193
102551044 782008435
922526476 778861523
712565506 882366618
74344032 426238421
80311238 652929230
623903234 780147942
861391181 12011812
860772571 771440696
86748961 507238913
274421799 523151878
759865895 984050000
821897933 409116630
426773204 110702817
806541304 999421122
525256923 592193498
112546314 480324321
226718286 35072790
259185843 939283792
769955762 186046230
218038566 850267001
838975460 694458154
482931296 552882994
558986321 196220221
176840043 498251636
703459134 451261843
21403513 315841382
287828196 695817800
724958013 714601400
806520617 384015670
566538875 184293893
976209168 679085190
664618215 202927453
566674334 923804058
994727600 189146449
109850287 65282519
39413449 801342102
759740674 374861100
206741449 318726994
571081321 383581493
816978630 127056808
687359690 690898497
442898191 975187886
239232651 20372557
542305639 45753267
404388227 108844513
82563515 380597394
640446057 747181730
436041201 59636744
523502141 430768800
248783194 485868783
496051320 140712997
139727238 108308347
368090451 346468687
427035341 939171772
582566534 96530324
918744935 269926223
639945175 214159479
97630462 879177826
234532036 492452455
777447448 638920263
453813323 860010963
19517656 94259379
607192692 308075211
6412478 130694832
738844012 107712026
469079969 87411685
248425023 608807207
195720032 616515475
955275895 475271727
408203600 390358782
571802051 179464888
660285006 64263579
393624367 610431822
943441406 628156403
102884277 720888853
267076665 556697600
433416169 139110675
503473333 40608860
447185887 362402165
23820046 38546252
470114191 345416370
125957937 718539215
954223577 174194323
187571043 762015825
649466050 448290997
152374607 73784454
627755886 665175967
138048033 21380252
275607788 81489438
649536656 231008419
654894645 769129675
787706019 88310813
908240351 143695706
981436028 207942591
506097871 857772429
99005197 976212063
55705152 77479488
547267631 9928728
251673811 587355028
771944554 753656215
35646024 776835515
827440669 663401910
442011481 818005056
537298517 570135623
752010849 39351526
801144043 259421847
808481201 441366415
200249015 569237905
585062121 34201396
777180496 943676347
891973825 876185693
772404763 947678977
953665181 172188747
810124060 57855345
759543775 434584967
811511560 795189799
211420481 491468582
311108063 505948316
161989992 848406580
76083938 914000841
887758106 877227981
173422687 548755660
171110750 373671702
117993565 756172871
407873099 747690415
552365571 152363277
476392462 324770333
952558609 282573996
496959080 762682668
340429342 109019208
49783988 4457255
904209008 261204469
348442192 67833424
767152785 510432184
768756358 695753077
424433024 509030817
425497412 450372065
57786476 596608162
824043768 28296395
205297386 84433220
775986811 757662958
89312851 252379272
82433290 41871459
534953268 431908725
657070481 727898964
540927933 706854469
732356220 297653294
968058938 80798411
218003072 587728076
443746949 986759430
135997507 868179973
495790246 561494919
171068391 406093077
158103080 995112159
434389472 363400466
932061733 210376282
121063423 21374584
315271908 56013068
63246043 850225177
340438147 572832879
430640494 733882434
279687347 15513067
31535728 100262639
96311478 102055154
540507069 392574781
88814584 676504576
113271107 437121184
237999494 284339499
843214261 248618928
131968011 277603733
612019395 64029744
340496369 585599172
85404328 655768278
494128594 1166725
358509808 687083095
426515958 789150302
420965529 706203306
804663370 305017611
658982299 753491202
407072765 199489367
146065983 348403703
875993944 259337090
785524888 966509792
543676589 628739148
215128720 675644601
758859235 679664469
592190699 99355604
117779994 530111381
755123882 611908589
383794460 113633689
151508037 810310419
755300345 572473566
369030078 559963714
730007531 28012376
165971270 137080296
80018097 312037253
338000353 956012041
423890697 123525240
775038187 967567287
604780743 990166907
495728241 363639977
522347729 87918939
315511935 640127723
470546674 70635816
104552665 854341134
36785859 256060703
664651552 644602559
828534269 33681629
57082626 411058154
914210360 223053896
400654804 994228458
535091149 738655157
802756852 958981847
862180398 577795038
779065487 319477494
420478298 127310081
683117471 942826027
67745374 998629407
435470104 538292048
921781577 540022769
245149535 811083791
796083472 909801088
308202703 477134095
795999071 365285329
888192249 562725785
588339226 288847052
556954242 123430374
27502208 212227447
934928575 742198960
790022486 566510415
61676453 63017137
546336850 597310279
858359519 614082224
448456039 293829622
4890625 222753969
833852391 250040161
886354114 482452217
12357602 194556816
959586312 660873027
559842146 847778560
223598811 697725
989141966 633069407
124128099 869160528
845296855 911573029
463875842 487835694
330599797 378068649
550852831 876936648
975378928 261728703
343535225 276351320
555558325 200942205
351621644 241927070
450982366 237975757
724379287 315856322
285048928 536481952
976729349 844891074
236776865 52844514
845588799 225918830
685913921 822233252
95079357 531210775
586322634 411471553
19046468 769438786
789540203 422415654
498891787 617435484
684144357 842427012
893786805 92219036
43369216 97924802
186662460 346867936
335900559 911041747
662724258 620949487
300040052 491969961
318356914 536816917
544814475 16462066
762735747 230728395
691211673 710331458
614455525 130050660
121803011 486018347
899489446 763859568
908434001 398381232
381295051 445094712
93324598 127598209
389830102 989210169
225523011 576492562
188594459 413939925
340050662 851318717
34889411 640090714
195805031 205762680
176907630 740619506
74741100 792159731
971347902 765952773
355007542 438319780
896003434 329326907
924338127 795492879
93186474 685288482
46390465 326997880
130383193 139715063
454596089 372729649
981441586 532635455
949222211 170036044
946575380 289272872
873871116 833981145
929363586 69676146
39743824 958787570
810295653 114484925
750947300 634159908
732954052 105954841
72479687 628957485
287798103 849334168
276966718 380984577
534622649 175873537
707982457 517522196
168104954 15094900
890251845 149546539
547730355 691990409
172098938 346822088
981263281 45970053
180803232 763143220
115646199 73063411
574447143 778458206
40064690 177910796
265134467 773018742
136381992 190130508
254492581 424180095
39464676 383975653
805164672 426603679
559849190 365663483
796642230 727954144
233274737 539410428
877500683 781005092
231400837 49599620
127827179 65180471
948086028 161146765
680840046 916248582
86726530 255287188
547223141 126791220
433197985 812357609
752326317 569579977
855004471 6818897
993760072 746985501
243310904 651441097
26105534 803160094
869620934 822747764
531114237 102895670
362158191 261131273
736417116 446075382
163247248 716760649
511255854 111333275
877907415 44612253
880098211 964633945
299899441 427321352
943941520 585613780
92195314 696267836
7710110 947199785
555603087 1470181
546701640 798913991
505427633 572807174
454590438 227564920
395554937 985704675
330460591 610229482
99352301 66877706
56304864 115115903
636154710 420077072
78965533 366578478
464689325 959063744
183728776 764588766
238901449 127670295
202718900 331096763
676454485 210429010
130812902 84573925
64415546 677514542
883487916 569843179
102838069 190594707
797408099 498393006
28815735 980385044
108622487 128168037
899779105 17443705
243283940 535933814
437520777 322249473
902512292 902210102
133829571 86241067
519315222 372731020
66427717 722034122
703827784 742882202
932463132 687157040
827456128 996878678
217187935 563460397
419238210 320026004
754055105 69162663
818419010 782870840
49547706 779557851
763555231 801843165
649517911 6839171
190293332 87038687
181604998 92805623
841765144 315434569
31563045 213596719
688165590 950507117
788147195 244509727
545905672 573126680
931666767 225878153
422521712 1371055
789338551 841759922
321397059 395910009
763438939 139816068
31297202 665503000
771890273 794852434
467346164 273924537
654207959 657639497
213479579 688329311
602961474 55244722
3763880 487040873
121357795 544445824
290064343 909504990
641471905 835970016
335148023 425655025
61848168 757669735
427026080 703703073
451946011 748423139
99613081 215384949
740755561 983426639
880887949 365162187
630795426 200750467
639086725 137519738
710906318 852566304
825849049 166384145
760327380 682129283
653425019 881685175
79091460 943489362
643706518 720563365
631975731 978854541
146218389 693823900
589040630 573244469
250043326 40986640
174183961 202172762
108887943 914939522
185599400 989775893
280101709 816394826
43042713 919188434
953914564 753949031
624271091 632279966
920333176 384598470
314409249 426274548
118799998 393500709
222280264 615022870
114064074 854255995
446393764 112798817
400596248 35434393
538559641 650639575
76421033 712743602
852812337 37825331
627683124 890928091
27601223 760301187
559839270 923160291
532005974 366270187
529625675 156277064
998550153 302475204
393391888 165475755
728749753 512191886
558976465 803546371
127214755 525556893
510318719 426124873
490872064 910914968
461559267 29431704
414070896 390496654
742175307 119399586
428321985 222374784
10327676 308439562
982675971 422683300
84116206 367198298
788953487 613741881
523475362 787503639
916217086 916867250
952979395 497483192
281575489 364472213
301029562 261306598
742545460 811348281
687431471 233417523
574779602 1507091
115365582 841366852
244520100 857540889
960766438 672842085
932432027 823610468
833798002 767624351
98810121 917914208
134822648 887763608
531656089 510814364
527783601 300389528
280197967 333279349
797872720 561773456
697751562 98902281
675596408 292813375
762766916 215544232
526230898 190062872
217051324 641596480
31429723 461571424
351653722 844712516
986929863 136602102
520839337 820727864
904226453 619649459
591158426 39049100
359929420 122814514
402379818 887713021
275720396 682577785
220992369 73593115
96867594 771260285
25011750 772464002
64073659 640295020
988008235 442820912
830357892 57575912
84417391 714303970
519147336 288587468
411532839 358593552
425189570 784888530
31837770 181932377
257054342 622996196
73497831 616983763
598327064 475877650
504696783 874047460
158455434 578205507
947640575 255323029
349465791 825168679
27787030 266055805
465463698 868311619
708876717 148337944
925887531 645810462
715158268 297551220
934397930 126691106
656144773 212103854
764095990 687982543
394036231 21150332
310978738 467534062
638134095 909305802
943411712 995347232
635869615 954383501
573552738 436026543
62222883 775534884
261195221 90009913
41590688 579175273
810837887 750467405
727513217 736725417
248794220 295187838
34276637 35708504
274395298 542937764
247812358 38491288
230920306 494364943
59641620 394415398
961899005 550292069
156237553 757827071
398155654 792107168
564726925 971708393
228133710 626949808
599759630 341845285
569476075 641350318
921020558 380313961
244334076 501050129
969555733 493128296
796237967 856348724
528836800 70633265
399286487 629165512
109124553 482723147
123530454 21282527
877138545 937945814
424090950 33376097
548289238 822246604
825483265 113016162
646471350 906133329
739965970 98747333
247978613 161958398
740097651 21515524
542272360 836948081
522565653 364344446
182592731 318803620
220693169 711429531
241953239 472496010
193111397 203594146
955219157 316641851
77393027 832357701
107104018 501483977
718250152 655393256
176246934 396249770
768409418 675234639
302383098 360891741
773981972 402878065
522850140 366595977
424393589 917638854
203544057 946959243
281983299 386136788
118279216 355192822
950082674 360232455
827688832 143194070
563826601 782907988
312352275 641219628
467782042 419456294
142703604 38548547
74849549 171466892
434798317 695775322
846701531 737181415
56667062 473199857
140059479 432033556
839795834 416969422
202188763 43339890
363928664 484172062
281993033 482207880
839364884 84592060
842440335 519570069
227786130 258783289
154994410 540138405
900002917 622776452
959594699 895222875
661324999 886960603
66689767 96123315
582735924 765907652
685821084 491919340
91623862 678396917
776469251 931419696
95366339 978658014
827275941 311811357
315346430 109268973
646535592 7227667
46377387 341492280
526797737 274163517
600275570 681792147
666818276 500278486
157084953 478929329
248017715 818409952
365889931 167223836
767049622 801142209
933131488 305387059
145577902 24755350
836300331 922047153
808691400 784183024
900705167 635967340
95994380 68567950
597752667 595046326
75795617 644130054
936538607 602593354
770809925 536814176
284385501 437628201
889609016 441470454
916557530 137626730
112396759 134963814
304850566 731962735
936106023 90498408
37349794 81683924
967770113 726166479
856247432 776461512
510349502 609468952
264945206 458860236
678036902 715214227
53906562 753832519
211860635 842961523
356425873 982670560
232292052 493327728
272815114 121901067
934798182 41888997
112044152 899711295
176852811 416894718
631674030 965475188
359909480 521540178
899675467 327679592
100223010 755922898
956657459 610572512
217908203 74119018
921949102 895945105
789333245 828372018
649777623 1193879
671333540 858719850
983864440 903625592
352047577 109195907
878043014 139362112
151084905 990087166
39073407 327937716
259498237 523263791
145929258 619407718
897320323 45604724
947087310 997543333
654043976 756261122
460632198 871952179
830380140 382581299
767897283 619713385
63469671 270191259
473423618 734803211
128911109 309804411
490945157 333475040
419000319 221504524
325353507 570085224
211591689 216943268
898022940 471089926
740207059 43952197
90497643 490043735
942073276 890101308
487587067 596117251
498878783 948219265
320585783 329258923
183316917 88483065
801488662 246786588
211190679 274912279
834106154 192618142
584716691 177567664
378609536 3717009
399072188 703963043
426318587 610663877
920906311 176857880
934270157 513629723
73326432 877284155
3673457 15399707
619901816 343776878
464033313 118780598
144512496 784619096
300555875 327829414
725618516 102044536
427132356 936809195
229473170 261238509
981943691 814189861
438806173 360553226
670423224 837878361
64516269 96741810
301058591 837938934
126116044 87845102
351568657 199442476
965129257 207758468
214842184 585031072
551535347 678875497
556328024 696047843
316010946 856883900
23877256 41629461
958928436 303525967
830955010 40917959
564764476 812898700
855107820 856087004
25968280 378047397
546481718 943000904
327305561 847540310
780939837 453421606
935385412 985024848
652864082 753031022
192783316 720222620
190578447 744318663
251614470 746906471
292882859 567625417
603790370 169276470
609254878 415235160
472802437 292726242
456153119 37566912
105624941 163777293
746170270 984109576
394341044 292651988
927110479 721646606
992708652 560566670
27584565 780610417
398107871 532965001
533641438 590891187
253187621 724219885
187726203 504802091
323642709 480609063
72427507 927433080
649885533 534198740
195184593 122687969
826924982 503854066
12771235 785066277
667631359 611457860
621692207 61972403
904109848 401319039
636135363 749334853
961885709 516236282
529945269 212509934
49201282 916103061
803401121 154905257
492839299 843643679
659707349 816482008
176769095 584651210
596431441 826654628
971366304 791616034
801858951 650807639
147986454 667146540
288390270 815617813
131120753 910082477
730106570 35230600
311401515 218758286
637081807 125803578
734994568 19543429
338313512 636712205
935646490 994230987
791617462 428485788
837874665 303841164
97484150 14643759
888492375 693915591
693814741 712375032
338047979 348190045
363182671 486034433
867852940 651572941
154168599 998973693
414171771 884275170
886720648 725573286
955549810 523802454
703893218 543060732
543345884 42206729
179772936 331508727
888954071 971390398
759994516 579345089
127747916 857478666
446505203 16240290
403910610 140319943
581131676 741958589
341026343 944314347
227993021 61395636
448403641 382161621
60369328 862575412
118953144 947089976
440665052 74502953
323408784 144558269
470080039 719271022
39281353 649852975
50779748 780751778
473759727 663290618
360096866 601507643
373285637 806602069
470264287 777196248
799438367 51395962
519154836 992981064
848226664 599664212
54376699 149146658
981825833 114746027
864238425 953295331
914352358 157419830
880314638 90277495
154494453 350394677
809548517 46292160
852764006 712844619
827043938 179040086
376135237 39657158
780547729 749420874
846259227 103328369
379133475 498213947
7240686 898288312
343711364 707983704
350468877 398088063
857130362 184811063
365350445 573885140
138106393 132219156
731304970 18421030
75013005 885799424
221332061 884561522
932091584 74096067
449922494 759135522
105652507 826057731
798792680 886200237
427994959 497568260
842044960 807128434
848298562 849285646
557933099 192009925
409785703 908401976
442614343 119432419
93213038 807964788
693317559 83835785
792700298 424622529
954773171 867713303
162938306 28621585
604791178 95029889
102717652 54713671
706681765 60886514
733287757 357990798
947086751 13799069
855559059 641648064
820927503 556373974
343450064 231376956
748383899 753235767
992295286 43514595
872668186 938024679
851479383 565985745
21860463 496696034
843124628 829149988
364409336 6062933
857771574 969200514
101092822 813005580
876430540 660290942
873892094 609718296
18281739 673495198
623517365 726357152
315143262 296961221
282731125 658593326
380854531 883631379
264345446 373149817
927145974 137013632
163690849 631141711
555515731 38067666
127837744 398640358
867217655 344763435
257219645 724989228
166480302 210828821
390511161 42910841
871119763 264403255
505145491 889401503
937898453 128662855
468275008 105558068
278140431 751006134
616667748 658994962
487153866 881013195
884661133 414299839
18026826 48351981
45441549 426058911
86419648 25795648
824699269 953637303
370559083 81918913
531142884 537039385
145264088 921654045
432466581 16383851
38573653 937612072
758301708 828988461
918791282 226576715
934546529 49448066
830099203 403730631
708443028 317253068
284743825 445620515
584069262 155287005
493972496 482027165
581345916 432908498
507822813 258561538
239062154 730898250
192996805 770205038
120453989 338260893
544375437 552920570
207161098 435465444
490532641 965462806
264453904 261840276
44555875 51516787
311288342 874655078
455247418 19731370
44424500 592507597
317868239 628493762
747794602 811840735
110520926 181656871
97265587 470860094
292734763 336327741
201758343 485731568
106532779 322212332
676508815 503424570
875132902 883669914
938890014 218181897
849132719 55860272
480022173 893688594
107377059 791310516
620860026 415140831
663558240 665284526
7648427 981426479
293778287 607959383
645783567 256815567
642132608 743049154
727675661 934867371
79376895 929434005
273115292 38426028
104162690 949624107
394366952 831811947
833294020 185773319
49993843 534943093
94149945 382532370
281148040 54043358
26359239 902008066
469184189 542433833
419808945 329348970
376376665 713587232
789824707 22160232
970402800 431957314
617725740 550594814
219341038 549618989
332545172 492456330
440561371 436707863
442080437 687444677
121036163 127890810
873217997 23546360
515350257 967367942
406078730 796498298
21411300 284954324
551022717 343111843
827388157 970831663