1000
814981411 458887084
170493152 194098923
473222527 856427999
862026089 664018822
78094868 152144769
648976319 465377160
105163814 122827157
626050177 253923086
637776335 425023613
379572878 224519405
161939698 716685451
195435849 981176625
355918026 661428083
237242526 736456867
121207252 116569912
309152291 788705018
427973350 332161797
982803941 753712232
188589795 697346383
270247407 266684663
849491153 919223726
732061824 954654967
894567238 210628354
61094406 384859926
488168321 293183639
609379331 650108019
9869089 804815181
483800997 218303469
318759617 721043524
954760336 439966870
690129790 116428980
81188241 118103140
448590777 63992181
724331726 489696926
761338565 994579133
756381590 463346071
913802859 340959767
270517391 660886450
404104475 331611798
45746375 892272796
624795437 655125706
542380815 487180880
312457240 26181811
705484349 631216858
599741689 512761038
71183727 289871479
481706372 4888322
260490973 930297149
68880503 984822699
272510428 682735422
831918185 28892017
146081492 598237397
222368138 416598884
259123846 626472613
600727036 157386575
371261763 78038826
812512282 913642578
565219706 124969521
792340743 123220408
608702733 244598786
488497800 532402814
534470265 970204172
537291136 647477592
753017674 606171640
484816644 25528101
141423415 316734828
906936474 287504908
914972226 129304611
556620146 26612425
608293579 157347181
183999001 979555342
235386007 849027637
745714273 653122067
826513512 390571369
776342475 435216245
635170155 117356628
967619059 22156773
87560799 357426549
669634365 840578473
963598189 6967362
718622928 105021603
323702191 625559401
245042865 91190770
607380367 801663011
117803195 68190299
811526546 154318550
900261995 46912552
3346186 498492621
552550973 682376053
889063990 181409801
117592297 376750499
298766429 937727710
251423626 386327228
147670612 921057992
79422054 111268800
928025354 798044983
68806758 104243898
276120737 166365977
47951022 736017458
820545343 18270572
804207757 632071888
172589122 556986105
531500795 28451663
55478725 84051767
710827716 797059070
117977923 680936367
26325922 416744352
471180430 277749548
803071581 618851043
51323893 735009989
582636197 979349248
385571325 503959309
936109500 661692063
522841641 984060523
250225874 343386983
2331094 54433631
827975225 27436570
463936090 211992373
55888233 519414816
148560495 619232303
168990239 266538418
152685023 195316161
683282770 623865454
473065709 338870704
95232850 524389603
73880693 530385401
356255204 459452018
34344710 292364703
973660435 409702705
128941579 223886309
753089688 131272673
130836294 433581266
158709244 594772384
645573640 67113831
966703554 794134135
686346135 135693792
60672552 839031158
331009953 743955322
315412965 804075663
82826026 410645815
180981619 9223073
941031217 537236823
321191445 827892281
829601526 294851880
90111339 958543106
371254543 843201027
942332133 502090837
129298646 101041376
949379575 774872286
20671562 916083129
569006420 707017697
904293275 482195326
546048854 87819582
78667002 861461820
891895245 14009382
124623988 72876863
23232455 918171559
462630040 344423900
598580193 144747919
491792134 688691532
103291024 863046677
384408912 898139512
217653867 513707559
851697242 167033442
288579844 872368804
935632925 710102619
579386500 839926199
192297944 977951709
927745781 270964946
691929882 672157379
284974328 816553870
597550596 160723137
587241783 60180635
505147038 185821975
57444909 996939172
874513508 13252287
712502203 111438773
911391799 930156070
625146332 763089041
97189511 913726177
487974198 885338790
476345149 67360698
577781343 668643093
897828761 358043477
792124394 589758642
30200856 77098721
258828865 480267806
90338213 846070648
392964796 595485251
884408978 450409705
444940776 611438839
463661992 9959332
722877612 227570145
940115403 348023944
990659186 889821268
114266474 331149737
775160058 590611623
251026789 205457754
111771069 148855549
563501231 903895463
591130545 446218441
833510539 849959411
926486248 923848752
548546412 171967397
371850356 285471743
474893456 669307486
896910582 938555448
679266819 619788194
18641946 619382221
820328492 9301131
361719842 934594966
192967223 136879899
377722942 443994012
194854007 342010365
592849562 758355239
98422182 36496460
204573679 931932721
886455871 983576281
708297826 287518637
8060031 932664536
572990380 482953487
601972021 322417316
274025289 133755193
942205510 292667235
753137414 615050355
154484721 114857256
402161674 347451944
104253509 779884616
791445956 151623871
121894980 236811871
909979110 72833516
273308332 114552788
4766236 12280556
950645424 565580416
299799193 958705455
350761305 725305928
441658942 952733327
47723243 715684231
86488519 842445107
8351465 692142288
457495461 15352540
659515898 859657135
362804484 616285761
492058104 154250440
767909632 466469438
391062311 530405095
539302955 664370643
497474238 396585545
676651200 448119661
814682316 828966747
259341469 165443620
554272674 701000411
970693301 454512271
269200995 909698175
296957377 130068815
454356816 606969192
145421355 113872713
319142680 508225840
582674828 811200784
514992634 203100814
130186576 906054945
733505909 522005885
422941942 83496500
918591430 952109496
531616161 585790099
781076242 790957631
751233720 187865270
344474395 574443374
642377541 466191745
484141548 791851273
596260560 938498364
398820464 594198269
904887431 717963145
102424108 340078613
381680282 469933096
395695781 364383212
228504395 129201689
886389097 651446337
65214544 657496881
456072186 596830705
243286979 89664781
240304689 847037053
277530051 437295439
421480427 772423947
903487184 758138329
564275219 352264097
549153047 815612037
946462366 306556831
386091535 901402829
646635444 767771818
371335924 42331224
132155029 599840319
24049268 871060481
103803009 89263812
528557361 559875195
538610871 624360694
649539977 631431915
471397747 779586382
68727353 745394528
552010328 972214537
503532856 968801901
176994987 52685902
784413938 123457352
211759088 23021826
24860180 858394532
790793644 248712459
753242111 775465028
701069132 629807733
499041862 804872142
571587899 27599222
217263690 962715124
504476270 719320021
594147038 975874017
498906403 515390745
573784898 903433085
340121635 77317754
872234986 517116622
982520011 509165277
640573975 46795452
532187103 517950509
905189985 175497101
619179322 510948449
803478483 320248454
993272536 302520344
977636950 417376788
182635920 47416993
380091911 687112190
766737015 826755304
515502561 118159771
342146048 89287458
21592855 682267684
19121566 746344195
51900659 854157932
108025825 692474634
900953384 640212929
62941497 658659722
668226384 682120819
22124524 471704866
854885627 15397059
626741564 832522576
285290201 809377484
879939570 665382113
349006027 499192938
344653770 717024942
617352709 686799818
658828755 638945564
221583855 530466675
237806113 273484515
237140960 345831938
818475503 138094344
986044867 881417000
649270420 506787604
416054173 523911299
978492470 123456153
391824712 457750387
955978730 677114914
119644224 688434653
195013380 468650252
40143944 539667150
38191547 657496653
78983321 697020302
148958570 300567177
227486977 386764683
426568046 464627937
732596622 245043548
455238635 571157842
978976903 957025410
77945446 247547429
480936708 908954270
371003582 872761420
366704657 179498665
402392687 486348881
867933318 597406067
807515487 908077262
137073216 845707035
418090268 216056538
542727336 567048839
369140069 622730667
953813522 795708115
87358604 686410143
40751662 395113593
110084339 872244919
204655356 188029785
119792347 685592064
96984054 490795930
410869838 316205065
670294595 813262525
655070301 390744267
263184946 462585787
151337882 400258162
160809175 569428151
468831054 703536512
136476989 837971123
178783532 942806865
633679237 118658490
481733362 526947254
513772084 591817701
251708526 718427440
779847486 371500874
256535858 729347894
714813158 519922050
898069314 237624106
185700928 553139614
628368373 448885874
868241755 632222610
849144037 29050930
54167114 170491444
585103796 43160457
8462567 763887328
985967322 494658158
882545819 467700683
21605411 248834256
59518383 125830292
967261696 691882223
497331166 76313907
273746471 64660677
596235957 24332138
302284783 781936886
577471752 930653157
83339113 298229860
415392120 932483150
327280790 469559234
102974594 912384586
512719691 963953516
528788268 498687012
458611673 411334086
818904050 332733439
660168342 730938787
458563731 479946391
275337364 808411251
408776653 549083835
873071928 5012609
573415973 175356710
639465849 3404078
958526221 722804963
301633938 373918340
507804466 481431083
843477574 463295414
246332022 208713618
279765283 775120290
707400631 738376957
38970729 378821034
923626750 699139071
109759820 234706834
31601816 385097184
43118084 440378469
786697373 916190012
297907432 212629699
944063076 789889636
216033777 902589297
365210952 370184070
129023990 873015418
851615153 825017919
188827186 97947174
33731536 468592469
873067465 593648521
59485779 912038194
972469555 983112529
463693619 82229375
70335716 347811789
319842913 113453800
788190258 106540286
882160166 938614044
171686339 826223242
728503679 387720117
581328892 93714630
757904187 562869236
819246403 462035693
387887154 860589943
559982867 274135045
181698765 285566685
867783566 241184545
50121233 840253121
76813427 366331206
774998850 147149144
714142995 947358117
113119298 354849606
906414757 995279465
293463649 78101096
674019060 874483683
318337567 107864305
820714667 76241753
670733541 492477423
390793800 58620695
353067365 950776667
185272094 534766131
88859706 53055659
628467030 138980939
745825134 705280457
357828499 373340337
704945955 71971493
320698454 818065254
426821099 79629564
813344718 572801102
157730660 339880131
447284784 476068227
447744436 120515805
404826334 118477976
612993228 795620134
29615025 966060594
598913155 214887119
353343078 540289215
120459133 981810108
531786508 866284267
539606918 889615007
239624604 97069227
961586500 412839412
915134481 240923952
492468976 580995552
813725054 650199637
920875683 113526192
978784218 368620118
234041997 236126906
339614448 847035225
31747039 369229474
665612172 483176548
436632947 871471604
23465762 557092080
705798065 407768624
423376347 97921337
297383630 515517305
194990564 111486483
928356717 110125044
204926789 420825692
691120596 18651843
923541683 464512632
984694390 902325901
833132750 71252740
138452806 25263551
918287965 22716199
394493025 436416491
358409102 831125973
160404448 234391218
240734406 866202514
642159843 664110753
964123851 792059827
32144411 159114414
903546311 960501128
121755812 108473099
233843174 812876408
979641297 157384856
129905393 816852040
912227111 963038143
888104780 903196271
988301694 658909099
778428825 235311073
95325589 136837926
918953400 108246391
223745498 159687805
974448905 718421695
676314913 938572755
510481522 708459324
950203523 266544186
668960452 71959334
227533639 902803626
737352096 59691290
912704836 867257489
876543330 824931947
682811985 617164464
580644571 523630033
276073562 359073395
758941106 223915505
348427675 530410859
332161896 424689528
690098664 159127155
143111222 218929930
97699909 506109098
927389255 900419787
772653284 448866060
972379121 852703278
204186039 562247571
912394568 116890874
429505059 641454251
794339175 112317044
111135068 374983746
488463431 387208630
586573495 99920890
463640489 935001171
630331749 795802386
212207052 172946766
954929541 355318274
391876697 905145804
861427373 319265951
658081944 486597010
768132011 482977419
191816641 972318050
45224989 104211208
941725278 327246402
598181814 736064453
292079800 709316882
963564553 780543231
949041867 550138047
880464121 412682355
337655571 510795869
61001094 549862623
683742636 868446989
757697252 75619332
626109147 471640978
247401637 284191090
958237988 868050002
767168509 2570983
692884405 664909852
106782191 634609682
992156255 557480359
223190488 284236054
119313595 39271394
64779285 68355461
589409442 797759760
333554170 779581367
161071983 247071619
181960344 844814619
115518607 939657596
772950305 741627754
411298573 872868296
878335199 222052914
740918297 498020061
224623897 286319055
162929913 183922443
920928737 7602521
593919156 996635580
291838575 713232751
35906973 209134214
634104566 477832769
6893974 820175091
257414136 20482311
67246709 439374480
865296930 35281670
231548429 490763588
776909425 642847002
216148237 507760977
717416270 957066534
5781037 942040168
95901942 21227304
978478965 16830678
28829825 572398120
865982612 320668401
138147225 901889586
382318969 624768145
232238708 241729297
444943235 489652844
262211608 364706298
781543678 127508537
399987969 13092106
470788479 29413747
508455462 686936716
537174724 225871732
496519603 542955761
20428253 592421545
564183066 998907218
461768578 593012891
423821691 180267543
766197646 414485270
82157128 148516615
39253415 166912191
390245912 336713004
656565035 652457521
701419303 290625067
632482412 101407271
303717173 955787246
130821018 812172636
495240315 667995742
890560722 991759919
63467856 910988975
436697817 480167276
762412546 750982749
73180167 38750590
931250293 691894167
453235861 865923775
840410782 345005630
32835965 83173048
681718634 541917355
588146923 383137936
832542422 73145688
337061561 136259594
28932933 467882579
800948584 524173249
988394675 544025659
368449521 51862531
307530987 657663692
384546161 69943532
408646441 310242682
961210478 192413087
2136849 266962692
58336861 695063985
611968322 91172827
778237033 293686955
485606536 218900309
529341246 318148957
292045998 866402807
306924905 320978931
186801740 960389844
697668534 175196414
504415502 66118054
79575299 811946490
576298101 464121461
734406376 984944542
774364143 548133207
29873982 629017346
815095899 88210843
324081331 427064220
31900024 954834718
573267530 517506560
173735027 102608775
688171871 465781025
969011582 995096777
639276310 8329675
808002974 336944844
183526090 164934829
255579252 115617743
976881319 831877353
579739204 563804049
669338248 206619701
111937255 699212230
835637047 779549509
639939428 12234731
59130082 671839452
967069450 632397612
41862366 993320831
735006387 730034237
311618209 556534323
577647367 950894519
564863998 238166694
140355716 600906442
403101524 395934969
716524186 232499196
80328675 148779743
796303245 602183278
355399444 760756855
153911861 43552845
392822717 793851289
55787576 451952799
318207095 875373380
84350411 360069461
721210564 671873152
942620052 32828772
80923828 372783773
983723292 645787827
610950467 124079007
99210622 14051990
372530330 815734808
246551187 305375360
964514552 895370786
907558638 172430349
508643994 61470498
215983194 901466711
855321788 124287125
353419510 26045236
852176859 290286275
386114697 573387423
962159427 181251102
458732549 43083255
554034875 294972194
541387436 164985342
271567556 640598058
31553686 644097886
456332866 278104873
949473246 273363771
25992013 709548237
445794120 534636007
771018736 661777315
436102718 478856877
638580794 642038582
504902113 490757652
932324857 743533164
916661429 894484283
924784266 375393978
790083892 478819141
670366172 331471327
496320837 941933728
972069386 527874523
438547968 280918605
805979397 240537567
554282376 831971410
950085805 76495
219123770 573620894
514370164 655226488
904994125 5467311
149781423 262412591
496224964 82106279
5945754 265402746
829106917 930730020
640796724 619190808
262065514 163679250
803178490 758386351
958129332 627764229
138777228 249193653
908682834 944756625
489731221 315481563
629244388 292333379
168074412 848368158
718470627 534960931
356111000 623464751
540428242 505892423
885877342 36653205
440515057 744339450
154572306 269621973
527585823 795369030
741329135 789651338
811564634 544507624
400554042 769693966
24788206 539331270
18887618 933471040
336604248 361135193
101468956 818364990
505984926 122059723
519249502 224455552
657020654 875360502
700436657 197448895
233769278 438830352
86618455 674284335
183169801 241190761
796422662 710755625
889076145 537751797
352923316 700640779
934775775 605993712
322851098 959563982
145324982 194255070
745551375 334445584
407906618 847020332
5326928 913891544
969080055 524576430
138347096 478617062
252453285 691300107
676065957 486222563
130130459 615200766
13023252 165816614
856391527 809445914
876572239 597984026
199714064 82011908
151141158 134489839
688005621 473992256
946570175 685846957
520763680 692121549
872808895 928670298
391658234 878135823
842561842 213254642
402712252 833425292
691871704 655165537
377241752 220454015
993904455 507372211
835654781 6927706
673188826 544562662
668889974 402277418
142546687 721120393
336805681 146204199
708126586 24811301
620196455 654696760
563174612 140960134
199334662 288499860
922146787 443509251
166635683 617224982
656763893 421864289
303166627 201151951
77029826 680408379
274122320 923450635
40296944 109777100
782894695 713485770
506856116 304301022
968279542 501919157
25421414 305085222
648123356 733548000
182412877 120836164
240761113 598103843
114312653 292612130
886603704 36459439
736121381 53239386
506200775 245401627
327620029 809367402
446553578 257166209
489775780 720675898
180616843 530072724
682969353 963511538
96074847 42341822
120328914 64354389
396777334 145750328
221955965 44900689
731814683 256885197
18253208 972575796
854989040 132565861
117704279 741592743
21541654 853825660
647348483 380258783
99227287 974968513
189626184 398297219
84651075 531918318
118973117 265267919
61991042 654458824
81295810 10582243
549317000 201624724
927452987 946094334
199891407 1925306
843511378 931706090
258810503 861764586
756798239 113799542
846846801 874502519
707908640 720904809
728328178 207773476
101163591 680071819
35258342 143306129
78369038 119909418
675224447 49858509
385177337 589731843
556833687 318989501
452830441 106150686
520614226 380283427
52245020 720505633
382208733 748272752
504728076 641019236
462553691 261526314
607335133 161916845
136028832 315243772
882821654 716873365
523017248 836501599
249461537 558275591
832324082 327830575
678185009 360064882
230205438 915878700
949796726 787039125
234868200 255143520
893189812 607998780
635426947 797951186
181020766 870152035
398740291 685748842
363687624 861293982
947275157 971022757
23210826 935820343
138782882 758548834
505210061 661800131
447566786 754671599
72592075 279890867
935018528 603293438
639955749 165223966
519172137 442268828
952263091 606556691
697412348 697969256
214555471 185355649
348436795 395576237
55507683 747177086
81325079 271711661
460987421 881116590
242734418 484198247
669453286 381517300
95263434 27179701
895833785 542830220
634367654 968425860
822721087 569386181
424235651 315193190
587126501 943407788
609978372 391905946
402480833 159907074
89875201 617036304
345262723 290828351
865128895 253286760
890521791 798970328
524998421 351509212
532603271 620249193
688223813 54572911
1766493 783487248
81752612 750116632
326317467 716120266
571058846 1554908
138022800 995294497
169264452 725149302
791218639 779242824
117055247 193699471
939149898 59446802
663252129 136928974
202791507 528381023
390215734 93313298
179867705 767730510
297338864 712470976
387979702 985562677
767043887 242262549
621566278 848796499
992379182 947883746
417433118 415954381
801955008 407972273
411248877 971219460
133121574 54983869
750462283 102693175
248683340 542128535
14656331 911935469
679057509 69964193
292832846 69273243
15793845 472700551
689520107 165649063
37687880 77499808
3728093 804731768
172278712 625294372
506044620 17174247
425694471 923477739
433128628 227649478
183966365 696893859
51385291 169604293
751877729 801847574
124813822 561068
196492462 139470153
765012892 875549972
61950700 910362092
797339569 77744545