1000
421639537 911563318
736166797 959945771
397431507 584367626
330835287 620406496
817678629 907749208
147148331 441099065
414206288 894297657
883204559 994445630
524103487 876941786
562666726 818229033
501791565 928639889
365987896 862835700
940759889 987370864
208015128 883900100
183345975 824073500
93213278 272088811
545076022 956824219
340359024 841947795
647306703 919526707
637770068 886278573
814436008 815619394
293893018 301164822
623385747 681306102
703906052 903782839
426905716 831766607
707833433 931220861
5223999 377611869
318257118 962721332
868946655 989930585
680731295 958570365
622230896 961368796
589734141 855286561
495495728 990127921
918641196 934518977
170576324 523348884
874600385 918988813
133502516 235546850
220918913 723828952
975662025 990819966
322304264 492293538
131348730 327689722
16577823 563809835
793543520 855549342
772561721 826568256
345692896 960558101
657211611 853631169
968008908 982784786
135115870 561000288
284262868 631029901
130231912 206281692
918943021 943148526
96848388 228268266
417674287 904626802
699294152 754057194
116206693 380376233
632355949 867433219
889379486 897826291
155711418 799276726
292123701 928157870
664049867 983067081
949661330 949724510
872795982 974162370
543593399 723191221
908620487 952753218
528609504 728661527
394143009 791214844
434000709 691905771
387024779 615224604
845588809 977918909
771955704 794365551
179064772 625624269
571329520 609848683
682954150 862686464
371854480 957913412
935292949 963991542
959589299 990375834
85591520 895551377
145351216 688261477
123098677 886821842
77520965 531269945
64654256 771828170
180666413 460536776
714793193 936215147
273151420 382428984
958471742 993283901
574731578 968263403
631912630 671656127
632205085 759990999
598021733 845241931
565678871 785001503
839012842 877136055
432805203 523230622
179621257 863484239
814731902 999889233
468027572 674439877
674738407 807887454
215508156 661017700
835151953 931216062
963756928 999989779
472078285 715690038
794968322 985069866
137731630 801781772
527212120 766053801
560989120 570802450
195969319 588317098
699998395 903148736
208760361 940064498
710176285 725850502
107315463 833046281
709311757 956731512
464404293 765787205
729230255 862850007
402453920 917899563
212633998 760124513
238036491 799557581
327284963 725403664
518040269 697058650
338203515 575562092
858043178 979814387
523322008 808850543
457435659 775510530
507810174 679442648
163127644 522752286
200243421 379213469
213813941 761847815
607879643 983075755
632997604 681135375
364470172 517835844
564422392 901471219
575752290 970520620
473022768 673164313
951067319 957293336
224211104 702181527
503613266 978919225
282295383 320560630
629608953 971864638
969513696 984068701
781671309 926710360
941934548 994938199
135544282 261726707
769513077 788725558
303889993 387679540
155675048 970327740
283084808 412382297
49131339 394280033
959569475 970133805
24369484 261850311
742181998 847108077
93328530 973670929
508836146 754194157
848291539 979038402
243927285 350400905
419020521 761486074
202531660 619110055
435285112 852983461
961742713 978066610
84815882 526172571
182534855 551603119
882156220 938915473
317874364 743288585
621171736 966900065
293918746 883184396
612415521 910242531
18124089 191078794
898957175 922258200
136616710 891010743
103398719 628617740
769902576 778618249
97227445 815446005
949674830 999112479
883769140 963048339
772886876 911072750
503388365 902678486
806966347 983069917
39307494 891807817
678605355 849125581
355387324 754490905
534263138 612549136
208526686 883083204
669315350 957149793
86662661 192944885
102085473 377266300
568488110 652482925
234548490 855355965
713049191 782588399
283454024 323067379
245467003 558546580
724431565 921217286
543376617 787600376
446119060 668914835
37610370 487215313
499056285 967753551
424075297 762513791
754290409 919910367
467579530 475722748
718134982 998656650
624720033 994192915
613799099 670395857
672088485 913796294
24607889 622980240
641258652 853727910
314682812 739085039
901091075 938752564
774314877 978241450
935289754 956609717
246108662 709707731
647574804 729664233
403959399 751359647
447509012 502834980
335187597 687897639
660102862 735240839
675425818 916216522
527132689 564785302
451716093 632334796
952017187 959499129
222586385 676777963
615272997 752718613
51662866 381894916
977253299 984316782
319351008 498219806
341075068 346057888
689531995 764014609
222379585 827499062
761493966 973685532
23251597 659395552
209290604 806447136
545917417 770060926
288598883 962036637
544560284 622443407
891235737 966372627
952299343 999473121
989246187 992367641
379460136 444236717
227327715 970808655
122503831 381262736
725363087 752973137
176760081 231847898
974860348 986366168
44424274 796163633
270107724 500880374
636335990 940548099
337509654 915191657
710831504 926149819
849498349 918628387
893401560 971875314
949740798 970791207
929511255 971972780
774310639 798096748
932217598 943276741
915774442 958817341
517013775 897591091
213298902 985553035
202295264 559372092
667803130 757545765
169679460 864350253
112233587 963768519
197376532 373676926
311367107 880072242
221177389 229395172
556462641 670963014
113711393 931523657
263004498 364253057
288165880 470726186
515342047 614851597
440932643 745218420
355568276 363065792
718279670 881253280
418387803 511791485
128669123 779548423
342217017 391908574
853935675 993693087
841375869 902595484
295012733 535176460
807339498 857784226
7176159 232459933
310750076 915239561
457321721 466076341
357893508 773949351
891402605 933257029
515188757 704193013
890546107 907579294
392876742 516310765
368874449 694032014
838307342 997808734
30780183 139280434
251013450 380661565
418388978 580566812
622358459 668803009
735774865 747617301
679695743 715295412
719831846 983122727
928191779 992752497
189356112 549227618
109043728 754190886
367261342 783187965
620534058 762024430
573338431 635065096
797652878 884791333
140177214 433367925
955409237 963985892
10564787 934998315
101734496 831719737
547096021 625715852
501798496 744828059
263096082 767608138
570321259 980246734
698755474 975036336
569100876 822380721
45671606 566140078
734076100 969314888
875819515 895532175
125445354 733985582
764805340 915307613
854678694 966917176
548425215 560380010
670684377 939448759
283066195 764333513
121298494 253159085
477063298 806551844
63608203 207232816
692967416 810871446
232046740 865524172
169653053 282041070
984128980 987634330
437561633 762823363
255263409 695275352
937508872 979119778
601974373 970885228
1461925 843161891
904732526 919030581
894613068 951498000
473530254 816675635
831110686 971810314
256549461 473332805
841281965 869270259
703343525 957797418
42404424 554862339
444378652 629615752
680860993 893769180
707143049 912893681
354627973 717747800
27182467 720626674
849482970 863648660
404448086 659787279
181062032 838544550
486689141 998841290
752368124 841074899
976707760 995349009
62329564 91543785
323611563 374177094
484297123 548495405
291341889 669368696
714009853 873992001
720841732 857796430
99544176 627746713
6198836 574333474
773898754 998928629
619701634 730339724
255791921 593277157
890621727 915868178
848748953 903526330
866125579 906256820
458855954 559726645
28443097 991726019
752071592 987080859
983858342 988607160
953871134 966364330
968828660 989773172
750215229 836567200
394756038 543325598
563733921 999871351
222326945 821858780
892970198 977935799
878886821 982966975
1888865 173364597
708789268 906165703
648280326 819872091
174368353 595895098
697556898 908037219
725317265 964170477
436737772 890212613
318572073 392962563
461538608 632054866
218234227 979883036
163800482 468730405
979093914 984873390
447448895 838966912
540405896 872132525
728604682 985603755
124588831 597511144
25886830 432863902
417188396 953088637
315484992 379591046
652352724 775339324
418574050 767811439
957883434 977614991
401380607 678040060
477805670 866993642
738832262 812265633
342331363 514818601
838936617 851288140
414855876 638308552
801320484 858900394
614864695 943766436
264105345 339098496
233471388 606607409
70635220 96639098
3274697 715394891
865842410 980454900
405850811 964288324
794099553 797215519
92226385 214229273
321173073 553251578
729111516 766536722
970364407 974179045
368481603 562312425
717065129 957391103
226896345 379790842
680944348 723311603
895877691 958693997
335377722 895202196
233513964 540655335
702195543 815797228
315060600 471088963
235992212 486792708
270342842 753864490
256584101 339483221
942222442 970725063
796179468 835429050
41904485 360562538
134986349 174338704
468406101 772110870
84137859 950486755
495585863 716643059
572161033 666760654
382695920 573468408
64882308 677069342
499333569 579048819
107517602 411942772
926449862 966440273
453195613 713211597
451787644 570680541
461342828 605591820
575147600 962958899
711839032 884171333
864690633 993422555
356388895 752365788
362160443 833340492
27350256 87641472
436120081 546667081
811210768 881289766
605742129 966957867
217111857 327257100
798583725 917434136
703889813 940338387
797147517 972740175
501989647 999793295
762085844 899979009
985747019 992003261
807380600 865062878
261657638 926742143
387420031 894421121
722794491 939117195
940863265 964948355
365668205 749492073
596817817 969694249
624615135 665239577
435679258 918354775
442640336 448130575
758468773 935838115
584037356 774259356
183913 645056997
596517975 603157598
815013986 836610817
951303052 989983127
29254405 729809869
922573114 968708035
545176060 978517630
726979886 858545174
125684787 222605914
803252730 972712441
462616463 735445001
679028640 980776741
899572004 989643762
730182926 738617797
581095684 874183245
263024483 538235477
398525301 571255037
676518364 697008045
713506669 934693171
828031562 932136737
876359935 904737365
846594031 915870553
528433615 635049843
147383869 880573067
397046653 665709648
838999184 894741794
978146103 997857841
943153360 968785010
877703045 881173032
972576351 974356348
614190340 772703702
427956305 964597563
284017353 616067905
566425275 852330960
11884201 830459996
814718267 957654440
884148336 946956983
948422830 972313419
505659574 662540358
253440991 822583288
65707850 73574362
867770576 873427198
169379470 743212578
866328947 965323457
371131920 545018386
273615311 830913325
435901765 912890801
998122241 999577590
327244710 796718386
12265093 855377228
876013293 918931821
670969956 920601983
386939551 696058978
559236972 620680332
623299528 778891354
159410369 502393190
873183444 929772274
246115055 479480816
303512715 658000763
43930100 694143982
527503780 995327264
656286475 925958253
711725279 794909380
765683464 902959487
525964512 892694754
818339866 835559145
17645929 452154990
176365492 784846286
538918632 951925044
522465893 596871383
865142333 961006067
35304116 921959650
735773905 820484408
517079714 860765486
300433978 358931048
770693177 819719402
82969242 199033725
903859604 927503153
498715691 662901283
130334854 719581168
677295960 740398705
265095367 488778767
870029148 908174956
635626387 660360582
177248274 758169020
181681576 213976557
348540948 397345881
89378064 204108438
338446461 908604962
178078473 889793863
727796994 834318349
688997505 955786454
273593663 937465161
492595465 582349241
602687971 823019017
352471998 520668656
996224402 997502036
118990706 503841838
58433971 334366433
713679369 833696403
714452880 893088437
927608862 996367428
103319052 205883107
847308784 942367498
381162262 584023424
132066117 865780079
40588606 518909519
452395364 531644844
87943636 126541358
989408915 995691915
670710606 749736194
437036119 894092827
60610977 125969554
455545039 467366120
499706864 747632588
33124010 396874626
242024540 946112175
503628544 610697718
395271398 872363592
228299256 370630188
372580197 619397328
755230834 987919293
733860972 895321817
536930501 819556403
694851189 975944207
186520399 929902798
870495659 953671147
790211772 802865528
13003930 876739586
254487010 534679144
92263649 789769388
723612541 727475022
140884338 986498373
594828325 964012085
112560461 814346772
289913070 994657554
116279653 471727331
746479627 813618682
999321314 999782708
145351169 589412659
351759047 374581951
869767595 895770166
821935843 855333583
437466573 438943909
415413165 985245833
144020569 259158347
458195534 989796732
741170998 966470454
558685903 747949529
979054532 982805442
62465095 717090198
478398186 961539836
370414008 619175760
375784773 993123635
417406995 904040615
574845665 692963040
93181521 805219129
841068931 929562213
516486533 527990656
909246688 956325634
310750492 753717478
770762133 822637809
38387345 701685664
892274532 945529435
79436360 112036502
777769423 941922631
815222291 872223781
317804284 639840693
85344909 226803717
330584899 438056069
69574597 997615660
171379480 477791498
651268438 906626062
497864751 508921082
743919407 936712191
370360314 489047370
190628835 833828508
263033229 735343292
932564135 999103547
21977945 749011074
993550889 994331981
259252794 785214501
120787483 257937542
384810835 434542216
461493541 649722447
343872222 363949549
885747398 893666577
522397872 764534354
738526812 746092123
847350680 925652411
734786127 819077939
800737699 988386045
22430444 833039221
707723759 820650502
793609568 866273816
366763492 857870543
896480441 909922811
326090580 614355244
858802820 984962654
429926554 591673692
228577349 775967556
688684865 799790540
679442549 696979127
477349307 517204943
388486823 712891518
47434653 200102063
985114897 992456041
580844837 952403021
263584736 455622376
650390350 987230208
502262743 579886638
425337361 667864078
761658294 766333962
997287577 997974437
479874158 902593121
425905025 787961813
107201650 125115858
804823761 933097239
41447608 886053326
352405757 703645206
294091416 526557611
874817810 970376651
249297774 311272292
845725139 915098395
995438082 996414262
523148741 994531785
14311046 852723646
268980174 343705089
24881444 673579756
63302916 987578589
754342342 922822155
332146811 421321331
552872109 721864844
652466047 714334529
858032749 883511250
700085823 832985094
671293369 979050486
984073293 991937344
697673077 911822740
912029038 927395005
294861386 892317843
137429549 408453805
117897878 189034180
142524046 235158818
251851743 681899480
811524820 923186019
499743644 518911122
331039598 690556905
2312556 361181634
344517432 491326208
996363338 997969342
776575740 879608547
230782953 427916562
886844975 912244162
618147808 779360381
872452023 972398813
803201978 890800264
783502149 875407578
391139913 635916538
904271864 959926377
867199705 913478039
139182736 771275519
124848800 260916100
794577635 826320812
68005810 557447728
890380349 982920602
196638580 366384837
325952220 407065688
515364953 688781524
88585340 291972207
332380721 796990616
602713965 845333989
561133841 786075921
387681532 791261492
417178034 753520819
800641688 808957892
5163074 911091090
805934422 880822410
782894794 860940291
650988012 688943521
299745370 647478757
744222402 997233887
80622939 167857055
914502199 954089551
510095440 547143542
368790088 951022331
765886306 871662253
442912638 877921474
323270518 891153710
175277887 277697882
204940247 365621070
868315882 982617977
90665508 416697893
397016663 991677064
828584028 901397044
234806690 745285379
808090147 980051080
894545388 984544107
10818143 14778460
648546286 837605343
570636557 999434774
324019373 575671003
762334935 972180915
466112914 656520565
135387823 324816767
109100218 481907418
972775821 977210073
68369294 660779320
82912220 359550488
862088634 900172479
300222798 995991214
252035482 418847979
939597554 941938296
716284717 913685745
2564257 323318369
858665520 920047723
550664296 716533461
67617993 159804985
148796422 360664749
91460695 614745459
729661469 892847162
365529803 567588226
69547063 255562071
575619589 718001929
822045974 866574415
219744307 980729437
841774228 933540076
237883868 442161220
557543088 878515769
788715334 899381131
772178359 855526196
944912495 966613131
880463363 961164172
573675619 986607143
283408334 774840275
219567187 533143961
426991910 735912668
420059579 518432454
460390550 962158365
526791168 966966264
335136949 605816416
689308287 764567448
216383581 756064706
764090098 851874900
620801010 763583644
168052634 938427806
165926754 170934731
561943803 984851793
459115019 543158553
816435597 963595180
639578499 913157480
249230817 811711315
821716313 887073835
810366602 854447467
341333126 367671932
626439644 633846456
327808704 782103783
133278924 733549505
629453182 802994437
441132864 892780256
2633990 49486777
788994556 802708914
628537994 782926919
139218444 320609665
791811405 963216844
671587126 861635495
300095405 606639007
826137660 933517036
939770040 952977649
813182017 935453369
68283573 485967629
113197304 280983608
71634423 579314522
892893475 952557737
191107223 277932828
121466415 767418560
482224556 635997703
417744479 458789709
285903038 377434940
511709177 988851670
648661272 760297819
563573094 996569321
749070756 798828781
207530090 476142235
426174725 997794842
104018372 842332293
208786985 828164320
596350396 714666777
428038208 923532461
174286972 342018455
975901375 990411457
969739656 972384664
452169345 507953193
744397109 810340854
33515021 260967089
934947542 963225228
756071930 895775828
884918033 975744960
786748875 905461944
123875921 638384366
886911461 957430387
151049964 274121967
307416917 693340938
460245205 468912916
456638498 469476883
512966204 819213414
351141493 428724468
209031105 803949461
635291691 823384511
50260401 221197852
695460053 701678293
957956419 975657596
116757923 957635455
434100382 958856195
258248551 606311311
441324650 787867462
366688579 433728678
961234767 994566369
691203441 810502505
254399670 538561113
918789516 982831483
178107831 989417044
488860493 986381651
672950004 785222119
900340694 983727403
98511019 112065829
45850818 388929673
84498513 285404860
410145320 631033506
779338631 874492558
153298180 928527629
311392065 556980426
680415264 777941463
812429264 951255717
929394781 936493229
646131060 706510509
550406032 927189891
254280521 378471406
764638452 932739103
740291696 782687924
798625504 940311647
824739783 959795390
400920166 582758929
433748833 641195809
284087100 286546082
429653615 888512190
40857640 160361491
389654568 631216741
721508809 982471864
493727908 695737066
760322395 857607301
404580720 470904494
351706316 555227303
823376655 944339447
872772826 958729590
468967602 867044888
203961984 470639276
639394704 664075266
410235707 619789912
533278462 631116654
837269626 983944115
581336902 678015680
357932568 628313511
989893339 993037837
406597787 416268355
696409826 829194049
373511415 453149747
623644245 777791482
822869241 984258906
926942892 974295198
281804911 745454631
49935 733683431
174537572 813870590
314690843 574789660
589054433 899241080
652242695 741925464
883124408 956349307
511864151 800282939
464488102 574770703
367696243 522864193
260261634 832753490
787117898 895309456
439574849 906339191
45822478 472349079
353748405 796172975
353483807 724189568
274447172 858673637
465643974 762573474
392226979 929129338
207853103 597447060
442527985 946170788
359430569 510922270
643835502 897030163
984736016 998665371
262211125 450940492
563528209 651365576
668824103 931229390
935316631 980158780
278602756 501648571
281947095 427804672
761195918 947887322
374546383 600342726
389437484 844023111
964765327 995503274
703504894 845950896
169620396 521440708
376626036 847528500
951823578 983103205
984100426 997261337
948296803 965590232
245870447 519958124
88160108 292424293
666014631 963403170
302389670 603548901
656271848 696390356
814914658 988351490
723839605 973783220
182403545 315051033
4765592 691738609
624948446 844125818
713503146 844386489
286313171 932835844
359507041 926733205
897775565 979763620
575525691 604593288
669453409 945521129
255810384 574002794
226844537 620900291
82944562 376021393