1000
459961701 778863108
184807385 131922901
981443367 130232010
858676237 295402608
970097732 646959792
948410954 11249484
654585213 40574562
621412241 591290293
164700773 800776111
103396418 272846788
439314615 885943986
780539419 596200841
567580335 596367164
675371682 284520895
432575756 613632292
520519454 745053812
245011753 557843193
876976713 78971473
688075203 735652949
374374082 510689288
235129094 175301389
521938772 889714307
68392305 995867368
333520953 233093078
649159832 289433726
358456220 88474446
27894065 138995638
537191642 595474400
587879157 212563323
879995295 872971267
678711969 253031102
618025078 923723722
810874295 347518144
2695195 351465851
83171092 229585631
714671493 170816541
257403374 89126618
60530847 325795679
84993985 394051801
411405112 734153818
683485527 769861332
675144618 711379592
761373325 212336259
159370345 201768835
277415937 39365639
74740101 956127906
144913095 545281534
732367982 808303744
892799678 587579531
12285948 828487125
817165162 726957441
999303666 74568535
816084059 59834512
252880568 901078045
306402667 664285680
487748216 842404548
286663366 15409187
406300493 48036690
227745447 565670838
249805525 505161384
457552831 177061980
313805643 602465926
722343514 46173624
263286023 615143192
633753155 275571971
296146670 303434670
2529411 295450335
230519559 818613471
207801201 335916482
572207869 366720223
202161 912472439
209124770 139381881
927881626 615425264
187418571 8143426
33612455 289740450
513304810 491165287
466802431 827110454
93631212 189145944
725800432 209433590
656805490 212069941
485005561 952952160
515504611 487534973
100918848 598540525
158664797 308720050
934457007 583389020
675440273 787175522
495861458 737081397
926557404 276259437
205023014 113975974
284402864 238635470
256232779 797707674
729800757 723035210
477334481 675948323
912181154 55651267
885381913 421502998
267721208 370387474
374455157 783225819
710438801 475374006
234282697 869103598
636610410 168739703
305008971 164567036
955915226 800870429
901648433 734988983
77129865 106671447
701481311 214049083
345306917 957714090
11756757 75107673
680749299 341607592
603572350 445446807
397258859 488954263
866949805 664980067
711858091 93921315
300722240 422296891
421811675 535004937
143916842 58422084
556260995 448925813
222989120 364692574
102312595 124637553
99681556 31958814
83825354 801162867
246007898 281648625
611393311 110281009
209272652 144658963
304404955 812845002
590105770 701663815
154315618 309571928
219160235 866173709
256009598 372398829
140986953 677821273
907403767 284903795
736243358 316181115
586345962 811748832
680873689 688658557
788902739 780555245
573133726 872728093
434234465 819141624
6893071 45627775
781938987 216165723
42803093 86343941
29010725 632908863
640524110 183326343
794997146 859684346
49500052 51006743
84599528 43003359
728828016 992003295
327907155 317587727
160700763 914253117
129336559 841574452
455428028 770755652
474646050 28561753
496000099 908880516
700219731 502893170
807024645 334675071
719058894 849827738
421019012 748069619
335252955 61543122
783912316 130250100
773743822 685928722
33773197 858343350
728932082 615117567
702862999 56839236
932705295 863563762
823608707 914558208
557654568 131553088
537830213 32300617
12631195 33830311
793697487 565367280
536723482 453238486
900042351 108298729
155582577 173577717
856368348 490835532
87637193 492797017
473601986 861381015
178725739 359891537
572240718 907657821
975009105 127620070
817013411 760230753
843700187 493138471
527305314 401354754
477207914 65135526
286171725 489839109
98965838 79869212
55206389 488205674
533107698 807765094
596504403 688690275
981342811 305389104
32042161 68980003
798186121 358160501
782877372 829428214
718052039 207634444
589602388 693061143
335254514 259132152
305808249 31471054
752270624 833113563
432825808 81994891
898249089 718997534
571834000 849731281
651383100 479556743
190453308 37007151
139838191 639474065
725697426 121181001
944863169 610255941
42677359 595565644
968416443 825554731
277510211 686468481
33189174 867112600
232045977 220960043
126244751 537854226
252431097 731031729
223484142 685256906
813026620 121733230
256770793 237376974
823980866 908153893
716933717 866950528
945161044 856771908
506424593 523374823
830469264 303804115
133630764 873146623
751886113 954563561
698701353 29396324
493548395 584406882
896508924 725594372
805366925 875270029
115964951 57798021
606301758 339449093
595571281 271844731
313698677 852342074
509221705 990195897
613012320 78671776
857146425 410689717
935443684 216087371
786580895 618429301
372407840 772728013
491575923 124293953
727291573 42793630
6206631 73356321
627200512 902715555
798950693 285083790
630501937 767431998
342881811 89320048
106881090 938453093
361164780 273096121
643311520 870386485
115808372 108840194
949058261 972954797
372046265 737018299
41558521 158627159
355447599 413966361
931355172 699539877
390776668 511163098
742333507 396983299
584519419 222050372
152215207 235986465
507134162 782717145
3418462 702532327
872037193 962815907
493501773 233201972
88428382 136813293
103588457 204236754
98169841 905163072
29707904 470216106
642181370 71266425
481359620 850145324
337749140 265231145
549685200 728525809
776394244 144535060
125509107 213430016
219101786 130240669
301932836 726235948
912957814 157867652
281284628 784995006
120683559 774786402
870713333 61628295
764116049 826818144
118381403 862285890
731981215 148089307
185018349 226678939
71872086 666377969
76824262 262137580
931609115 479025816
990663389 560519712
476077230 968688851
626466082 695179016
98929519 928398918
273931317 864403687
86266570 555215945
501915046 59466483
330002346 372628378
121094778 94118394
51962875 91992535
808920638 783944091
240081842 846455342
863139384 164470282
365349664 792480000
426607862 149475132
124022169 269787605
709994844 600099399
90992809 188977280
295278414 42438682
117376197 569209731
906842369 56159121
124425675 408757414
115625604 306944376
633902147 89236736
253579124 685865022
181229271 915016117
322325466 273827467
761471458 185464849
438297749 126821121
977944849 864905612
128812608 101967017
134693216 838807452
554582770 225686025
27784731 849861184
268124707 997677284
271587268 27483429
53836404 248529298
436240843 21978363
407990028 70142989
111215099 661569152
608524366 144960725
429101622 930849832
418788192 43089433
116314681 857085942
22426909 946775884
721991553 151239517
901259256 709201123
990046969 308358379
934887148 870348055
10735917 55528208
720541692 282323185
83011637 774378096
383368837 371768834
796356459 791358865
294428178 760087913
305444371 902952544
905048638 734545993
833802375 323836829
777635427 802633410
33439124 800062336
601925648 755430677
951301853 355701257
317148153 793865175
664059636 104551654
516729583 674795553
160079862 237271274
809635093 95607853
864165725 193003929
467376688 513038537
984362795 761804866
273126449 142323519
664757409 30691440
876869512 351076137
354528270 654504938
6225901 387967394
307083627 460667903
995914426 258385479
816369160 313062578
52250654 332945149
417614233 421496591
860257057 430210449
658767866 669892149
525818303 375449944
715412432 993194991
888488481 552291580
754999856 14131284
694615099 272273618
44822724 571484611
475866109 399350994
78505902 482092010
639834743 385589530
942759913 635749168
496491363 611645426
801328100 401258371
797106930 71458686
822754963 657363986
501669136 334039182
179772488 27487438
709489126 895184920
20682428 597977606
299992854 628198638
612108890 994607953
752988610 656931615
418608917 228854718
908798963 497114820
563463083 548633705
735220704 358739349
36899226 231712066
970384776 838227327
632970438 620008059
909686013 308241754
129888398 263871502
642280936 309660886
291358940 351770061
57362159 164557722
802264021 357355013
645272714 266889265
204479320 398261323
923820880 623088237
479632396 685136196
120203056 43095478
86286255 707940114
401834827 123185481
939652181 224735956
813929162 425138972
844744015 576131529
733380726 974632413
840003031 228178015
136809652 131361971
579948076 46688166
148436047 234728450
404043179 793708762
501617715 608522499
44486438 277954948
84127090 524118834
963091145 56846500
419730666 49377399
764786615 821565494
25079234 556955149
898817804 839008397
982094121 596078173
415139925 567991200
423226939 107659309
796169215 560036592
91537634 228633644
606724758 239973682
463362094 863284291
886198798 964979810
324323144 930685236
95451111 408450234
307320424 58542255
465296734 727051090
107919654 230083348
401132937 132998889
787038497 152467095
824523640 621648971
748545268 92179918
42156524 171772206
199839227 690842093
584325152 291376862
919475737 43566263
531350544 235354185
906850555 270065695
52850348 231173698
53267284 148301459
639623932 360587708
59360069 104920665
940155153 19796077
187520368 193804443
5311320 827075219
346271538 829834960
301240544 94816805
922014878 343397068
119105366 121854105
34239161 703430518
413230967 806231252
746996782 797097865
894101791 653847336
67163559 946952139
737537388 120430843
947769953 229677673
333534906 7130021
187114692 273690058
26926098 374635060
467494501 32237419
54226633 813766040
862072379 355467177
761099199 636603611
698864245 880204565
758457716 585619760
583635083 24205036
244367366 183148218
821302901 138469156
836995554 740982814
937937650 427049295
861413657 738223956
656726968 47464916
745353977 843841660
321154974 624796429
70993074 641165830
657033848 125219707
307448223 371622581
480686884 68547421
8226191 32067482
948751987 619200261
617687243 384903423
495921651 714570963
568051641 169740905
705556473 257563548
910723719 496010476
684612843 624653729
234234431 193856164
672118646 832104762
37697823 993273620
456901191 108690897
486955803 966451393
233910604 794404026
190590327 714597488
862951448 51332872
746664971 664219788
670533133 216868567
901639565 18971137
931439530 322207559
188712042 489512356
579771107 99435760
985522833 116900303
724089490 72273617
310756467 248724489
904378380 200970644
94514462 213795924
309661542 581470266
180247316 396088500
375874291 370837644
110685988 91342092
422170516 709867313
608078234 945220004
779252234 509717798
964191141 563208117
831925357 152903183
52720472 264212817
104855297 38243304
233629474 828944787
110516922 544385941
77669275 867411656
745356586 24700092
81207579 907534482
606170358 113971249
303622981 982044649
484808893 266825323
925903096 759495764
829208990 533981329
704715767 608461223
896215482 521423261
24185693 580657192
674326444 76906166
844870010 779181742
967665825 78499483
460642882 930699101
475401779 390828512
798110756 73274718
415528604 731834689
980809200 21698961
845805939 136948534
856259964 183131185
256290212 634679413
942626949 85499201
21177096 499859069
546476779 917392578
21282330 570662472
498049769 548125128
647568638 195436132
179823223 467750817
126451970 640466106
398449917 454370103
883810972 49077027
527644821 151855929
780911716 360970374
26071244 479234008
350435262 882331208
662365194 606725474
369526975 604992142
692224676 390704071
104851211 91217808
308096648 978649896
661880280 658662771
526775023 161965272
854098904 706598247
629716089 833067228
199580706 28166005
287437330 83391677
929759387 667598505
87763960 563187457
28568878 113835204
42421464 231520494
996166412 704786658
838245969 218209740
162295154 382986998
608913811 119662719
474204806 917010459
98312614 136085085
428189584 477603991
298050357 134804841
36718591 927766446
967872069 88815651
808448806 107825752
24723682 590724546
775424257 112487642
153912002 656509489
226322846 48849821
888029983 75005612
753636479 726275951
293215352 768447987
109262948 902129164
888110706 435984108
671655976 838939674
572069194 99845559
169060019 722635905
234650400 58294964
502918705 55038822
147110616 163883864
162864574 171834298
754608410 938288831
284321941 908520413
594798319 510644787
957370234 335344656
585650399 563523066
61620606 878865752
184487407 23399909
780994915 72598112
311900371 305167244
764054141 883969565
405012804 785630514
459121824 492179558
843925478 962040529
547218381 991036094
125924392 710082955
162870392 880532802
648371786 447192333
641569568 95686458
957837120 451456155
431031114 396003873
867495576 345168075
274869624 51982982
221084338 908380893
977097449 532984709
213548136 593667943
269470628 471077294
379298456 728592452
963256853 75740288
543149334 510475233
66776381 669073726
73074541 82163127
402122881 721446327
529355460 896208804
669649140 339708934
200181312 100680253
735712807 67676887
298364682 863098785
119659869 371965374
771479677 949273673
904950084 837544167
542941615 26937065
308621461 774756426
608045871 124394667
850496714 151195204
634869900 917273095
672785284 707944441
999436223 74908164
281907122 381308036
823633322 951556262
573533324 23814634
904752869 161762484
91491521 55633905
24861268 63667745
427599279 648857299
865457772 185065716
486401466 260915740
64519135 647539281
35672165 672565006
771933948 886168879
823760210 259320201
655958328 349061847
967264642 507910904
276486366 101688117
741735294 100119687
905760733 315268618
123934321 663029956
477031102 67942197
718663861 354408725
984126297 998779494
3266023 702100422
36361564 342183843
963016162 100880699
989723124 998688328
773445706 761657071
737373560 449722269
20977271 245848241
798784117 840758268
606275499 75270482
794962739 348010793
27906523 700723472
515795765 4357199
216269781 992826867
72299396 934933642
199751945 908942047
786229489 203017969
463558822 822591053
545201812 426574983
923471753 387441290
277779664 696917458
1614714 867669579
146639726 22591986
113517819 797940197
715866608 572309673
873210679 363345700
920320466 901117203
64069171 288632584
905474402 132855306
133975804 830290152
67788947 333727750
591748552 706534791
536745719 55307373
529125843 934463885
334398710 305113949
321905174 464694729
2031406 323519889
332364307 1187487
198628229 298398480
651644038 767011191
870708153 377371071
130356890 643544972
131004627 46942416
932177556 36479028
179797722 66153360
719285534 100103024
252397464 163550439
806637815 789143183
71374166 188280011
576123421 258289230
493393961 898028596
722983959 347941721
74064838 55348265
201645562 125209421
206263100 853289601
892220612 929487607
83177025 22577501
425548933 214181652
922036272 210242842
103177034 101833994
128912556 822462568
54453372 381310020
838529361 713607541
22969556 909903527
901887552 599092978
20709110 247797866
349637927 743693070
448255942 423702765
651557689 649901504
548912186 857820789
355707458 293649151
639824750 438884483
168743006 65373682
653066135 90779278
275616524 756243169
45129626 404529081
431222090 99582998
785839101 122267804
665706893 808808658
32171330 420110798
260417989 52880441
667908665 610055916
649089865 116164606
33758680 300647553
618582464 435187220
10984696 826806277
728836371 650809446
118207113 897579377
568699482 771273249
840875009 844316006
380032771 886004635
101361440 663771216
838103987 739716896
786039020 356327233
401041907 670726705
776438032 661459896
576123500 296863050
271515811 225213364
265544010 157790845
378377271 884126474
445494419 389361967
563449104 26847143
892687767 681656218
924426520 461387248
305445820 617817883
158219608 685478591
356338871 112097402
201766160 46959212
851814298 987805181
403286445 252856204
658531885 179724476
914316100 87171738
476587526 38348264
312385102 742131536
48655463 690762373
478774364 494149882
932640695 42223467
520997025 825328461
576396039 297939899
139232063 881841859
915757782 149968025
419836804 272096652
262065427 621602964
319055864 113879725
609408144 722342310
219252283 120456382
754583140 133568383
207628120 83687020
24433001 372529576
825818556 73088465
63291949 157109273
567238347 848448998
51849095 88235372
526293812 628245134
238691625 665525875
362603347 154449406
815493900 782440151
279062412 77559327
404043114 598118277
43955406 865967613
172976940 263207689
986423995 927560080
249292426 46568469
11247099 126241782
419098045 689582010
199330247 334906348
699207637 619084948
35871699 751056732
559836674 562165512
231818220 798528299
80207740 594421567
952977705 895701641
229378071 84556471
825777322 633421185
682674748 722249082
351905151 708168042
985456771 190845500
488244475 87265551
237413969 352007929
213507333 509028368
41589938 265353934
843934717 593313929
884438882 879806416
196887015 444275556
294488281 428705235
95320208 374696022
875643156 48297913
122914016 105021226
132854384 948691338
590958765 668045486
523456773 942863917
228729881 361429897
133709416 716974356
448695448 223639739
68982284 514719135
732668107 963088577
780073069 429119177
556402506 664511951
161441947 753289521
961303861 455930228
34511109 56624068
830626250 910154265
957438336 953540266
867691845 942809074
754747957 458650609
463370913 278204729
254030879 692100794
639634627 387740295
409075150 940846429
611380034 330573788
455565564 196564495
293662365 88154986
625683672 702581225
752666937 787125619
308387099 566487151
243055847 342898208
623111220 73682096
105568826 433065909
879738717 973260671
375874983 634486673
284427633 839245896
765207757 538458513
383863044 257358737
778715162 792938194
198205165 242611550
123511981 506287083
439176045 269690700
594442070 64859716
972271925 199625360
851985336 133175377
766112512 947557537
476073585 241740085
873755987 434158765
674805994 753494703
259935789 50680976
240497730 544363423
742443227 5705486
935338290 126306270
115580577 714053451
771760818 313785742
956665001 747789153
820072826 248357399
869996208 267031249
313217116 694784486
466656609 17718805
827959864 232769120
965276342 156549802
474509205 691548682
590708568 1831553
297559739 850644357
52512529 538057469
247524133 647472110
396279309 182862422
626294734 511859886
749432228 250571905
678161982 558613582
850877413 350751161
806970982 720873620
617782410 120188097
268174459 84439019
990423257 96134322
169724493 808215952
252684125 644233699
499764633 843392693
646065252 797324372
546553403 551094135
187898194 794077537
51082599 436693857
976939959 529893687
948553743 578888540
780465593 479232079
137502122 483859359
829983240 944473104
57249332 447765650
917177555 325423791
384721023 760117165
421558114 554445516
568333116 526758593
51195568 920614103
222667639 697260820
570454829 769221042
100871309 758353023
563298578 4470262
47563234 392754891
534363949 996116977
971643431 167345895
327865409 961661907
651205254 157848649
758651364 708454586
458130653 528345272
33878377 842851676
288462436 307952845
397297191 709311906
834711438 448492760
629926009 57379076
998269934 52897191
826600118 99141242
811250214 242415050
103611504 858813448
487686295 490491808
707446779 311846079
657837703 35312187
273507986 309042957
45677190 32159349
17497542 503807843
413020976 903892274
199175872 701483412
211845118 596473064
263311672 46556555
897482178 893237681
956451986 895752111
946134872 635568458
847409708 609901439
877983508 803537566
321231241 218186156
146545727 881194374
530032235 804383431
769022915 803540221
113426387 814700106
688215925 983440284
171024302 101236900
739848912 370200175
655236666 951694030
819189593 918548338
850766940 716671770
664302372 659735279
464940234 462953597
295303736 164866295
925371391 25803597
820920216 99118985
243989753 967465943
980313359 774021989
771849373 749336273
430078563 737792114
416552732 970810842
573748752 440093389
924564096 166114017
810293564 432317116
117808046 481999510
203381807 821091340
51187633 867684180
333342973 516127867
183154130 628646709
533510517 108525520
506966661 354430732
60160859 750956414
174413028 40474217
377494756 946262402
642326845 660089674
536570869 58879576
630900515 962835975