1000
663307073 949601845
762227828 860434499
613084013 927576203
785866095 830342436
832364259 921696713
411999902 798380917
989696303 994857534
420425052 640484146
817693389 993861573
927530478 976502904
117347524 574211418
880938198 966192963
428142800 498304454
542661640 918046254
717390689 904276494
953838288 980922588
433114786 766887470
712694937 722265022
893897082 941298709
638293140 701932395
494923774 627198335
183843307 520706073
729352677 974787287
647911422 790105004
863278761 917229319
588150191 624281748
685423362 967518651
664295306 974229673
830544982 842324038
77564723 515082301
701070480 729971359
725418770 734621015
681823792 787490595
211550817 323853787
305936785 517007342
485683712 887859796
984117471 997509696
610613670 779343025
13384724 867446940
655834254 834930079
464037621 771186251
848715178 910134635
590138438 614744608
833220245 982312031
780117964 953461955
329959527 559365006
656489207 753552383
568090820 850868134
567416830 666731192
832494905 846033237
801402068 934186233
755527023 953229429
626807589 871183443
965067805 966716256
864350394 995236123
582319429 986143522
702444538 891750020
788878491 938767437
857269083 926334212
281083465 352796759
761021239 796049515
63243152 245903027
339350524 423559519
206014003 677879560
580283317 716137440
942297502 945897882
595427792 675936530
458547544 833519830
651109313 674115004
461649452 770354662
795730704 837489710
60081926 740748609
495336832 681792255
408497768 481951650
223785502 602195270
705622548 847176159
770278321 827657111
205644911 351815948
519762398 730149177
658388576 889025860
593587398 729345494
171504845 409278286
763856958 990061537
358362276 780289628
670408229 774846908
861115508 973194694
170824557 941672250
503810504 837731284
749101296 917994626
345392984 387670363
32466209 612249992
644187365 747331038
688597242 923468940
329574367 915967001
338370105 770439795
938446553 962518114
241693686 569483300
957643716 987176008
622918995 826423626
683489839 887611839
154693260 824349050
880844104 917838910
818829472 882371262
413843857 506004484
494751627 867359327
3090244 370844986
92112290 995409498
295504204 823489335
566034579 885040136
975269268 988313809
149830598 189715993
922171930 989854922
624015614 827374210
209977170 896626947
477076784 538110374
716182336 846655772
323513395 379619253
527897224 952458964
769854437 826888731
381881872 956299700
352607876 649783775
622737539 678015756
730909832 812804811
543122079 956688260
634536293 995096569
691740164 714945618
688380735 989261835
532861718 691917023
17012234 176659813
159056677 659325149
86256730 783441187
786969334 952129193
524972471 770619803
789404113 983138576
22393976 210590673
849035201 900790963
174295016 428823784
807262913 867076425
695553778 718266907
763281688 933100488
858159813 976447493
494950691 877519617
864561721 973557752
722874144 887645532
807820896 891793446
26905429 769079820
457715535 836824991
850636024 878139147
842871738 888479002
87162480 857843001
16475116 990996684
321331882 998017814
708274346 812288681
168494769 903207591
211362614 325759612
84062198 255283630
590603969 935552648
979285058 992864017
620059513 939845618
263636646 326847276
462383923 706579143
730756715 953934244
352508141 944782958
495712606 749697538
799467751 851591105
79323336 158536696
72621546 983415819
697374453 770473097
387518405 680673622
623090438 826374629
29734308 29900060
868211619 959358892
980134651 988340137
63562141 643253035
590783394 652558890
907456227 994971286
427618367 726486628
560556517 862366871
984182750 988998877
167415720 907780075
986331373 986449270
907772025 963381374
321467204 843530659
398981201 440505503
823933296 910480418
13841075 825682640
647290016 677662267
95779603 911251612
850101344 864489141
880665324 982917178
401672699 869872196
669125354 895535624
426480224 934517817
186539666 199443268
533367205 895578540
916321789 940985232
203493552 282391614
456401701 659420161
94630229 685914930
686865014 967641670
842306692 884710425
448707988 687150784
950235340 990699589
901803305 912598507
239987054 778419981
199770581 668806372
21873594 478360677
561494895 854987408
812140416 894136149
111985669 878489686
992563691 997872449
345102555 647380292
55517047 817405681
942045496 974967689
393835525 743608012
26537314 861037573
387384744 742334378
980936845 988187407
111122929 689361139
29272319 777458450
66483968 498321413
740224085 882124163
427675535 468935821
859930182 967033433
130580 691634685
43897314 772255151
659932705 892949868
774149146 896684720
88469907 433541915
641164921 922309028
660040051 900603639
602915291 877318514
228902962 325012305
493264770 807374894
723200871 918178978
800463769 900264457
34685076 190061247
156929061 272568526
244883660 911474265
438872920 614757102
145847415 362042469
711503207 853932828
414918047 934929910
363811064 439040037
400907045 632678180
175554418 819890757
942627653 974324031
288542157 869426383
861208333 884233882
723933984 874791448
520086201 657891408
162425880 947802481
116545387 936509153
219896364 375802763
756425389 944116349
175144765 338236394
46945925 756349779
2433982 62140752
254756796 632408691
132774876 465548418
213926602 919045114
67592009 852189153
553190572 779894411
667300705 949212461
614459776 817674867
784371166 892731129
97299507 311616738
871898006 896735974
769545495 993010676
386935154 619466786
753145692 895501432
710730165 741219466
777440440 842517234
107839247 425710267
596943234 767093763
307476694 655600092
940104206 959623469
982554231 984006892
273365488 724840393
344240078 709647838
739554266 763415230
689608865 980068306
814490763 972575010
288628682 864113799
295805912 332887790
939946968 961596614
950862675 954212080
150137560 609926989
533560917 801277158
690863334 995225369
368935143 550656778
645695407 847362486
555548888 909142159
22576092 494983853
79097209 706658533
203580162 949504676
575541534 781495422
791183444 874498634
223030820 786706814
525617132 888679453
658212287 990457323
437863021 924170691
768744535 927662311
137132982 557475601
406483013 823239477
191697350 273564315
280856350 635982788
138790019 408996225
690664050 995482556
290604263 852913771
268947673 382759063
107808575 776090564
199386661 339781783
373683372 817026179
138533159 687856671
130431610 833743057
163983150 705443568
415965469 788475481
718229961 951176152
591700510 601097894
833246783 914568658
100130908 513625293
779829204 884014006
669742991 945415746
491543933 903437838
32796250 142687744
67075526 679961015
251692591 416235092
248636995 321431618
760624728 767946507
789495739 804371235
974448855 995297903
49208976 676585251
560637528 891006857
28576479 643170235
746419439 980827752
341012648 506634761
662235717 846587984
265395517 584774694
637964511 800887013
368779111 699362456
656206261 868279640
868838278 971004753
363457997 555709965
34030354 605766514
659501910 871850695
977467597 980830001
469384372 696666281
428747955 674964598
480210823 890316449
679670176 718319937
250810872 255421037
758575350 951440126
555828167 654385837
432504521 718824212
806195787 965714945
631700842 814540423
274831438 759302843
189854783 264674977
1713096 576637315
685097645 825897075
336688564 807379208
29592557 715977875
306854073 916923777
238951985 802684013
512615132 723780874
118534662 494208002
53028773 875290713
14405655 851086634
249558965 792545459
663667470 806017540
623188968 867836490
303139271 773943094
198016418 757801691
730824918 745033280
719457202 888208626
721867658 969488230
433756914 472129491
897789362 929290920
672907310 931962107
683531283 974961975
201066749 715788333
916738849 953791020
319424815 937736987
175590565 681246076
572311287 737703919
908463563 961647228
579991057 829961763
633637325 930278435
566096351 789813687
466852129 483758232
155997760 521033407
731936598 761262459
661932839 871336610
368764047 482568206
909186692 984538072
263798126 507953166
395983136 680679817
182026506 855991536
476084224 964894188
234968285 590724646
115470851 648274405
334677549 408203102
675786233 693811614
600962339 660763013
229821643 971160743
751316591 993313474
247165890 453810490
543006155 965611830
468107571 781526077
699856917 920831879
731745766 999776949
891436447 904233881
935910737 992942407
37724537 905658175
18299476 167352420
729941138 851611993
610895287 616793664
384604556 988295424
958339854 991123764
560455121 894580240
54164180 269088302
72643683 627426419
349032071 886899179
142117376 505696719
577714620 866593945
850351456 923198184
335743200 916214005
891573253 953070537
275463593 388088346
475822349 629206266
122896725 166289456
34584857 252513443
812752908 888086656
790909002 865192459
91064641 809642051
135519629 379514643
160366715 946442251
948513253 960001054
103878484 672529483
150874651 540331773
774405660 942349354
287414896 369200256
180285143 854907575
286245145 846777177
439001999 708781538
461041872 486728842
461489913 668571461
935250907 996358724
296037892 831106825
330231560 614273970
972468605 995577236
407454980 533449923
666659013 966102138
932379731 966968909
923565963 948035620
339296788 882940820
562539448 740837208
985972651 994290436
914159547 975511662
138638268 603088156
800962279 876310736
471070675 833702804
697456180 768098772
552013544 706039088
394608944 451329233
686952953 855570318
520947102 925308244
82872407 369777780
587791347 918705012
152308796 965588356
332874341 652350226
828328802 873738912
919744568 955901149
406794939 605290412
891386797 976246514
358924696 618597530
374432007 720587374
574534564 900910693
16531717 824464450
398823140 881395481
935685452 951258842
924320752 994882393
358736332 873698581
628583792 848496999
248502983 385371630
798072657 859742495
382899189 658865279
939802912 953523842
154403719 884139754
321597071 921633505
928394155 992869984
711665294 929176541
707212492 733588651
275961443 954763792
317641121 668997794
27376695 211781040
555801896 727537143
827180675 859533877
952462346 974436746
769399023 783371094
674961256 755939737
97442962 785017589
545565868 657928314
858555643 992671804
204164257 971858615
987135421 996466258
400608396 841628253
183881385 433565350
228653285 492459469
22272634 639449991
573553627 762026576
934052748 946591110
618163164 881581852
849073275 938731785
924717942 940322522
762860756 844701241
118611000 734375816
309800529 735579276
901279589 906145345
490230349 637947642
518870549 743680312
340794659 665820198
723965516 842732266
797927351 832193349
508567560 670294724
668373003 897499041
557099582 569556942
483157962 992289827
364081690 801583315
846862224 949564514
371244687 875612239
680487026 717473301
533282711 919494784
285206521 392650347
511399778 695337294
547040018 731862280
51479403 290560587
486082353 710170792
948365032 955667711
937145934 972518090
704613388 755625875
91701432 219626551
669438463 783332869
511242787 950057842
829569367 936374403
943085903 995005888
742350364 863595482
926544884 970073885
263998662 611227809
845274422 921923191
859623857 882764199
343468035 859311892
243091762 897045000
852823875 861196108
1636621 140323831
104474359 485272447
218095746 846239691
683931796 829272165
554655671 743477777
673184836 813621841
548968613 766309545
884202076 957289433
153443467 746094675
188800350 469530409
13908259 263801887
820507936 934887412
571387277 738774545
21092391 813655442
92563135 628600314
467078922 599035513
377026468 968527168
681377409 981866122
440166125 800144403
249611115 840871673
345100262 556386891
80074194 859871339
944192956 956405838
250391943 596800145
580329524 640261932
572313934 624270324
440874340 536122455
139988967 308870837
341980178 379830853
210318417 472817110
440203688 668851529
852507716 956295171
120592759 382032265
600353461 719384734
990336820 994088775
666445858 835739369
797176942 894914827
325816321 581128353
850329739 978079306
348304985 440970781
923541797 928627807
897105320 905894438
441315258 919379697
88289075 773312524
683957136 697659884
549406281 961239749
120431517 795530592
603279702 799369849
781730524 826041085
671607721 912655378
599364311 844162927
438533276 735036632
10135787 729054863
2264657 235504921
888107409 930392993
250403100 617770775
873208209 967974874
651737922 667892281
513397649 587276707
235744972 504362140
89638708 248786029
322624811 476471572
469577476 610609378
439136208 971336956
384535281 415357207
957605865 963613582
924404244 942158044
853326241 912949846
16132051 282786572
403599770 443150239
247129391 992900389
175045023 937471518
280745229 870279514
966211508 977621499
734745694 985006879
261803802 556913632
870930647 937044329
227370486 805413100
55063047 998631328
833359268 905832965
335966927 854399813
759768700 937948126
949486909 981199108
31089452 688187045
644899989 859883038
470129129 876273668
343099049 446906539
277339958 586363830
701293105 741713890
78209724 382984111
779482939 900594176
291966264 968021726
295487134 972920352
42881658 458838235
948026650 961698523
924547323 995198178
203473469 420398305
716641709 735899931
739833775 771090024
264117589 938080182
575422195 715993540
278409688 555166707
357715625 550060367
929670012 956728063
475529503 773290044
984207857 992464530
873790503 991062957
144877140 231181232
152007368 262810701
108579383 575091918
500549203 529660242
991414138 998182892
76739607 937956140
394469547 932243718
5548205 981029549
961065960 989512238
63525475 480898391
627592754 657517896
416741639 659167373
702931594 932814876
346614387 902308593
278131795 853517102
274455296 616692023
208935187 706313815
42122179 231369965
775295259 912887759
810509806 969806416
154399917 499234275
477344787 808774638
242955771 280351178
79533853 666274417
781852399 813565938
630501473 648118676
184874940 977417782
961337912 970546991
859659043 960429716
861076853 952891891
602618648 789264893
546660017 608811871
637697077 759940168
721523599 962296894
805655736 921686438
457262002 784811494
407813417 604833230
256133655 984325335
366005623 519948795
395745879 683155135
852475460 909617122
322055175 536320147
365197104 511392820
689385485 859077021
701330568 992676962
492344648 723531914
824561653 843187939
543423260 952640174
255735355 474927331
704580876 852331799
194506857 627978927
299518037 529007467
841101089 937592766
237510992 372114881
438653459 671595583
445891170 517250236
465892409 577930989
762367119 984248759
478138652 818646445
174117995 668322695
66838669 985599575
7550550 32362729
659071121 982351321
469879335 967553137
827974455 901217570
697387742 932110207
980676652 984936813
909313554 945561357
255016069 450543762
879414683 958599131
364909841 501298394
758394992 898077361
705293705 873195154
793689154 873040984
710187763 862565242
529650828 855384105
862828014 963281032
378601638 661890670
28137017 667143108
697867495 842479603
725441249 912250179
542669360 693558225
896045093 961459938
667433645 741019371
655492768 772090620
416976211 572352893
148988941 741876354
73010543 772999316
257883191 372732305
917179231 949264548
336509831 957006106
353373589 806908345
615656106 807351590
183550585 828964130
788113120 843624559
966792900 992343339
831664908 914723218
15819196 338766645
756440990 850864514
283153228 787294756
40528490 419109974
242715110 314630915
629642090 730115766
859452529 927017574
307931442 467508771
258270520 992909576
276815415 590864712
231536288 911858027
729514370 777860205
637145296 923165037
84612606 414122804
55500149 264311502
746089331 863025484
895592962 909933250
799891773 965617391
423386579 468380682
550531510 914037624
418269031 559675432
489574799 507834079
948840283 999072298
192729471 923387744
770759726 782555624
254213010 631873767
170969996 401678139
29730638 751439139
942868483 972979035
312974079 454446325
585639262 867696604
919556964 989933497
713308551 799227202
681763361 902549413
286528665 884931013
820725740 908996113
827173764 856664171
511851718 610741732
505673605 776585517
191142897 761023335
751410768 928989605
152552704 778058293
372053995 716602697
387151326 410704512
295272530 363319446
849112411 930239857
445389486 539395308
107408566 323595226
90609515 549162910
344026461 966510242
892732791 983371363
84483855 933400676
807684388 893297707
864861616 999697408
799469547 855408983
865880087 926985360
671973096 727760812
471478834 745497054
430778069 785610650
187747199 622706915
235522102 992538285
970642779 972938387
44921063 898156622
518546930 520673128
964643730 976238533
46156460 322186226
134293139 339168477
814131030 825782693
5843156 538656920
606380249 758797352
367567022 995232875
658078144 949268798
938510696 951570507
155515210 355188655
148819526 165722158
117265842 375256507
173026206 285081433
545463685 874931739
992914767 997024470
833637060 857656628
245562922 506000858
171377189 624193064
67358160 963949955
707376093 908821813
417942501 629797985
207319887 361071082
341889699 348333354
618859217 718799711
685315520 880136725
993536937 995174040
904943607 942109269
665653500 873391883
172067762 965643480
960110257 988204833
560234234 785535916
875194015 928936443
115853910 144379083
948639781 967008482
316073299 910063676
754808582 780858095
136325416 930549861
805426616 934668272
800622076 966535559
452128504 777651364
344197451 479532217
891722072 904504780
32591983 111377848
411237637 629029836
101368693 942339587
793386439 816485854
61895345 685343525
315382656 540180497
567298283 835330821
301698015 507479348
743253728 943191768
102363275 131583477
263830311 401770371
395055013 464630717
101676579 573145166
19842218 553749535
862086457 865144656
370225716 650886772
697488437 876027728
853607258 922940791
603736487 671372486
181816628 789467784
403825898 447002922
79510518 553203948
167875302 439152866
324515306 493268676
672573172 772194667
120923389 435732901
540798865 588805183
327281710 506375593
280832001 859130717
573477842 859354908
236638741 637532274
808832966 959470281
510864227 888735893
495018117 956125418
14475039 776114969
259607107 572870857
621783681 735150919
969149365 980129668
952819006 998784025
774176674 807544614
288571360 639166351
826727171 827646896
945908077 999691610
605446730 614482765
41972412 147184352
848913257 943857414
302532938 684054039
482580202 743703882
636485592 986502138
872135483 916777194
759940860 905512406
574073072 764280443
798704657 992386057
984469603 988754500
335021263 497923301
637349436 931426914
999612244 999942860
246246441 401448522
810092693 830614449
856941361 888100759
123278013 915233399
384544544 979144915
11839977 359762101
780046538 911023891
673151426 858616451
656971484 906053058
999998400 999999549
292100566 551674916
51402367 708969078
768363986 958353349
575609520 975378525
462732755 992616143
820016983 985327631
677161996 838655203
52373818 900654861
118376059 460479697
596546741 799067257
987207352 993735240
756731346 794330016
741181490 999095495
328490428 914825991
912064426 979790098
47787134 625724580
920400314 940103797
862840660 929205796
820739247 971090756
867941267 921155226
564227882 672529536
720473889 848672605
250115939 745991493
947340271 991393927
719238040 905475544
163820565 686850425
78844486 489535865
408816753 642120141
42823287 427194564
560883023 714584526
220035872 890217881
460263138 640394441
630045926 792013571
298078616 900123531
30571535 229575023
14149729 823280479
398803438 722279653
45770305 788414742
255033727 660130682
683281602 796678740
471976339 593841296
372811098 376035463
731797690 738676929
927341946 989247374
601166574 833581741
336554465 667401075
14296710 141380117
235934324 270630186
413843218 880643933
732972057 982406716
414876630 927568019
336445912 436968313
717285371 990234643
778818050 853134334
346468136 866207730
882041936 894238779
178071135 382998394
19916956 591136560
104525390 234606056
592172381 737440381
781541210 850959081
677345749 975458784
274285951 999619735
383530551 890004006
298846106 354959794
863849650 933325143
392528562 406475885
662224744 916200161