1000
661330356 52985058
911549339 118926429
807317539 459347150
992990256 125679776
996241486 82280282
257450025 582461396
44344361 698285094
556255468 481860750
27279480 963134370
360597324 244327895
1458727 313220656
28903652 638029509
779028532 948274529
822769865 991613747
474364459 754045096
45454841 135694814
807030154 809520535
107137597 466864047
268867684 952644207
445060177 117625523
887440843 702510202
700086919 931785204
253311649 256342387
266162308 280591130
71993110 626759632
524919025 73451838
792496643 406339031
711481347 571525174
354613559 386767566
415655274 681494372
140812661 461110115
669705540 800359169
123147003 629359491
119739569 392014687
434520051 564799746
509640210 321960893
119826301 62243483
106262451 373137951
318585870 372424759
653729081 390578980
851700745 31164459
464030818 644197387
437503490 28028519
68238914 792117049
414796085 483894188
326127775 555608746
797520658 995833315
208484268 920667661
625192806 328223838
165198702 59712856
893023584 674838912
234190104 12849885
737082395 192968909
385987836 908184619
565393668 39716916
151279953 269610766
70881375 615310771
913808154 360901219
643339290 834563422
5534621 58135374
170973964 331662396
466260474 968494622
327495711 674744743
889162282 805204871
2968580 54360983
717434081 748508518
581716250 951624185
761358403 171314998
144593093 999862593
79499617 562503115
892095863 83295924
832113882 815493592
698606695 598438389
176394810 194462339
285518164 181929432
105114067 456492128
513591828 423890896
424986749 693603893
98635638 166665385
498808763 954120573
73542722 68759198
555145444 507775326
20383382 169020201
679090325 17492830
168882793 611106296
432512299 60978656
694402220 117142534
728988602 245525268
568097277 905383413
292503961 853615442
939829199 397618029
310107569 305937380
821508925 587610673
999541274 772660917
754276058 350866390
579297843 680335134
419625588 134443286
188110460 292525325
155979841 719717139
162534509 324862635
183339788 595046808
238357645 877742008
564705697 967346247
975783630 132802973
725246013 268287591
986418415 517591565
518421974 149042338
823528946 192447252
736653011 823070219
965108169 343445422
26452962 396922365
23780555 446078551
383882005 64407369
738603876 539861847
784124508 901138385
717240836 967464296
348701546 955598481
697722657 913407243
775461081 526022641
46210216 353223448
794310232 885144985
870815013 165248559
886703677 546860312
357695811 475873041
222446884 175320333
819318463 248899847
572242698 695615373
694978398 808641057
612539096 433582273
201019257 249179958
187237011 918260093
69160607 535938557
726374927 766883265
449345800 354352362
145422259 348072370
707575810 939732491
85733708 430907176
104981049 972437386
977767489 315193214
300826780 52730726
490513547 120145243
301630573 62756244
668276970 996608971
723913655 133332419
282707597 924932913
382512377 469944608
843193005 451672985
5883165 422084286
71072603 307745319
776436648 216494862
655817689 336528811
8743706 594067751
767435987 113724755
419021490 597719829
281434323 719848271
650450556 771947870
692509868 952081129
687220468 213303191
801206454 411134122
346635610 83914050
188583388 729147988
553858659 31776393
180820972 412258178
306377033 251893575
720003497 82813680
468388437 228337539
419342491 477132143
822405290 39294831
443373252 241426780
489531015 724807575
961275051 139981570
349271798 506301272
944579053 36492265
719604463 598301860
300142741 66240072
682215911 488726130
795388060 88590923
373018877 828725386
500849101 679395910
80618960 73368951
762209590 401523751
301706490 34068434
731172248 124111779
73363265 27061853
218054913 415410634
751869428 31846317
407908558 101141225
538147589 205003965
990149845 257752051
803305825 290292586
176508478 338038089
779018716 971896538
426629012 4553946
653138278 779994467
683949856 586273592
853363418 298675799
987797344 155069907
332744233 571485945
131698041 258623852
598547799 349752954
674034487 202933580
381599272 81943044
156591160 919746861
139463363 146741004
30015266 942769189
289549944 206523744
280807277 68568659
30936635 559952644
73122605 684074913
339947110 609588815
270348505 45826882
908264614 110662202
200896789 93525200
682148147 332594830
352149053 133212299
682347785 878699894
336145880 63947056
813159292 492737040
836210271 952622656
639478044 866225537
895391844 929027989
72749280 28715474
850113002 103685916
588668118 775751962
787760829 781131583
237857130 910625688
826958465 146121744
21287889 27855253
239646944 555952391
212966438 444312351
689164690 747830577
323012244 25310569
664293987 136171536
370563963 500504257
941310546 10042007
219246148 689218743
791586350 291995428
717934217 494215705
248197698 159118689
122484020 35958527
940250272 360341151
799100569 619725090
358979249 672904813
500096697 598626193
81373557 713063135
42938544 770538247
313410065 218467142
648365171 977704052
207155032 18929133
330724663 981931
881487495 549970811
690200674 525590198
841966239 260651245
872322258 90163937
419769934 994806278
978638819 212536559
207663782 630255741
832261649 566643031
303160553 184874699
17785578 384534110
897937835 913240477
7588711 63864253
131707618 508470236
41568305 191379005
379915723 372292968
192360936 113919572
922263779 882561611
639509770 616746371
143212855 364348381
559426662 415499143
211671013 390581834
480552056 419334795
20837575 165330058
838494181 176514482
350204757 856279759
413564947 100658945
622036589 421153658
164523199 606260561
929623894 206091504
797639566 162055970
430900826 842516857
275975542 205680958
577594821 915485313
822427329 573324030
132350047 234370345
988823173 344021060
477468533 321891582
763355856 350822462
487221640 454366390
527336945 837426397
163162502 940901892
938085343 785199091
214571903 102608541
391459651 996712151
161216399 41615571
158768120 592117225
884132428 434743663
797798183 314243602
202745329 472741865
887567632 335095376
707112210 728907158
679116437 37097097
50798739 294988646
387919559 538020379
749355036 915256504
227963129 912517538
708674749 166048471
550232982 775763006
121173366 941692633
772475156 282389765
835824558 783759631
874506990 572473339
71019647 672305172
886716941 273764976
145047037 774284572
461376706 704675601
355708083 140493142
741772698 406506822
287998142 129692257
797043555 889869532
897465115 25006684
654903423 458656218
43571509 205136404
86935577 164744876
999345392 859410734
447134641 835169949
495686718 321641631
260159642 566706365
846463157 146876582
840471341 844026548
773677509 154364400
401218503 129385591
147373897 142991200
388408768 435372039
125199811 185452322
177757925 875181281
62975360 832661348
186353852 106546870
37797752 273289429
271291746 889659498
985216517 718426387
577345800 480903234
40068017 837505442
47609598 739047529
984382025 740597293
583074076 610575887
894961694 984292579
739961478 42335590
979800134 128370245
330223983 957516299
166338922 507981908
685213933 229314282
193159610 724084139
335861152 83473716
997373569 607152898
973133214 835106439
178095639 550479013
168526027 70680010
240500809 68651979
809727539 77399187
809249273 245317969
687975074 556727320
82126901 280452905
451579264 61927034
261339505 634319601
871959688 427678427
142301509 409689974
509509063 187977473
133774113 845370216
271451189 983664036
305039467 244584402
671286828 483135106
647579769 839812855
553815117 888080578
908464835 216059009
965479765 570230461
461376978 653454838
126957780 543503880
933907744 431053398
457947268 47763602
65372998 182423309
475442029 60190861
592113284 984951092
100684688 578403751
682837661 372135877
414584140 840393483
616720279 85870967
176044942 116816402
778200177 729860059
4896979 686665011
945919069 970376745
109411825 259812400
476347936 88885959
803316280 262772033
519939357 261263548
310535635 437828709
443686857 638494018
350535925 888316495
475961464 451220613
319236599 11315478
823356491 733820739
851708961 292593123
672208061 27753903
409409525 302924591
610130316 266822859
989589602 408565738
89715957 99001426
668378139 566063893
40403739 471694418
681352281 560343096
585474320 991887916
850688159 29161177
482898288 53740437
769994026 958859752
504961051 89230625
970175230 180833895
675567718 821884191
325943372 200292132
702154448 735352898
503216723 312284763
2175756 345322678
720850502 91891713
296840458 241744994
510471960 337244197
713439412 44340594
897587293 151430086
36228510 600791806
33107617 371643152
654532243 803101643
330502903 12009647
892332268 153194486
192843542 420416340
975078677 518786915
620708472 529749478
106656166 123925195
842034242 961348277
469247873 415401097
905756344 766088332
657146091 268744657
103332528 223101856
313085252 853436176
374531942 201830116
306744335 407639559
573473268 961276578
63257556 903976171
973286226 955589824
57170656 18646121
228522517 884765688
537433036 849230990
267031519 496605556
973156185 109065760
457953832 294920411
376983211 216226529
913525097 886645656
484971187 869373980
109747512 798056439
575326509 336795808
999886555 882070844
596951722 573359822
843347421 660209278
329852346 669150000
468315455 239539356
687796122 696837973
976821398 77745511
546068962 243852917
574351068 371741500
205435031 32304899
519178265 434934597
101047783 432703362
321580252 586018970
154593695 283844118
384075408 729920204
473156281 236478316
611991047 70108002
809838138 307854821
730317280 992206838
977004822 51149088
84262547 517317297
747987061 61083945
595062808 146572376
157453216 169413875
518313876 362888247
54235129 37492141
797822844 155282912
322711857 971919451
741301882 477305552
108279922 977893644
59742109 581436203
214371959 671733156
651544205 876726451
832104331 234377838
868933288 661625506
285526927 953195835
178942802 33513987
866796134 774005611
32602718 24249349
795935840 550916594
239653951 850170969
440925089 37476794
857970235 616153300
861912599 451788470
93458851 970192522
429682113 5717314
551628724 496570426
677450470 55689283
373296876 362071155
142583475 94746517
23696660 428110402
900458707 55155817
314140744 767254840
829161428 346743462
644020544 477613621
750176410 883674495
180300944 43617853
773667643 38271178
659771153 635580242
490059649 605746359
458289117 772258116
611463673 9917840
268828542 141430497
918123478 494641772
503501652 60706953
589388290 527198312
341333709 342363350
582354129 655474453
109618189 264031910
854734269 606155087
741645532 604910679
489829581 921946476
648528532 116013578
812734008 160816038
751593820 155310010
766562397 62399290
927568127 378026070
72317130 48913022
519456567 842956963
543554794 22958218
903663916 132943083
402672884 97513978
327822787 837543368
752988432 289957331
101575277 460239054
896112418 695737163
65149732 238458353
470199992 566194618
354471931 135450354
727010657 106065750
290760364 346089407
20981394 218328490
724115477 93298524
267241512 96088397
788771841 810796307
971562970 544952110
796255744 226752208
642466089 124078531
64295575 247970874
266552216 18387206
708209928 162664633
566640724 625876015
401122986 36840715
44586986 755594917
24807423 771597643
714177021 315567788
117687050 735158415
533896278 694318881
680973294 653654145
642923633 322261488
316966805 614486602
867213599 113222548
841238810 509679687
89817433 758050739
757650561 208886003
776437946 318376842
371550637 195595023
944252857 625189977
84952092 988839844
233301248 109759516
612953840 947478269
425327304 583157244
535153038 959223582
129992479 68642685
465394080 772916112
390904173 782360885
239919067 110634125
748099788 81157877
620313812 690433575
691724970 230480726
899319579 320679269
548857569 123386569
516274292 345626779
748576546 601226385
334466622 981877794
710985901 947420463
781872417 136313204
383094060 169541808
948053140 513086539
238184493 413447220
286002650 481605020
48324458 525921718
592239146 796424246
459595949 65069311
486857821 3837272
295550038 238693753
324516542 696923961
362080322 840790834
42550739 110656867
442017218 229533716
92534661 5519472
29470532 726923432
141832676 412564592
896465240 89885816
925651132 134649732
355849390 64170135
468771106 404173848
590091853 61010251
53114448 902204156
126079563 539972269
906041429 274145955
778666022 230557970
971069916 140746343
71348803 13620654
103919564 365882376
95670724 48970579
371401848 125141256
775894011 365750879
537705849 524875604
308153049 463356980
512041690 664002439
527527115 980812797
920692641 970135323
41823047 973807089
872339478 20418964
366295711 630897260
294564919 144961732
861455230 118151188
138224429 785320388
131771843 94660348
3719117 79958921
143630927 227637319
205100178 772041293
593388198 742806027
149433250 901541247
58679360 661474941
418060039 586206475
642287737 338752680
408858151 536627138
165076122 133713983
409562457 531371834
764611243 704127376
528849920 478582827
822278565 519590704
116419568 806566762
614251052 120138685
886525683 610398333
347776004 91625860
234955979 941164203
686948241 384389230
695221803 745627601
45864170 113281842
184350430 540668261
304550876 593208581
929811753 469626998
726922564 339374209
998831 491533807
896017940 529848752
970116634 570812858
49439455 86536201
229895973 516206861
59191240 116421655
979121548 259483598
60563870 66593881
53164154 600028465
450983111 748385958
345656066 349363635
861667800 530006496
742548250 18735029
123215076 672360002
488362027 702653995
864250566 489360859
46704155 760268505
871725965 16820788
183597716 773681774
955873344 413493689
142404988 867580938
382431698 121526535
127064535 295511922
188120416 180228690
895540388 491619881
928614648 93712807
840983516 642798801
623719303 436048119
661533830 599450733
108408121 2412210
154621081 825175041
491773069 201325236
437959899 216015387
70662378 621557615
989697161 26535721
35051303 132102148
746633013 417483001
106145038 873697549
712994924 294265454
906442593 461051665
785885336 687573594
554764472 479385205
182888748 31000128
915433325 844422578
630450861 876357800
846834788 785071943
554049194 191124211
986397179 992009093
407139598 57059557
613566707 249353113
936111633 501134364
381455261 535261000
918617365 487600299
261474902 484128642
634382108 167917494
945180307 272783797
855491088 352461132
752169002 38379835
383461260 520118680
735318767 13912121
248992833 434669908
651500418 803042027
478310473 490413950
647567473 885450072
399989861 113650533
134803184 188617848
614784897 368774799
723878848 385918616
708891453 985353750
870047258 343273560
5787597 667743919
616057357 713795039
20205050 220742712
604691228 256182665
593377747 192526348
122611140 842370580
627196256 774111558
497928961 105506729
117041861 145496433
843473155 369548077
111663321 830792693
558165925 726448218
52083845 134561126
112366833 760975298
972431230 834930446
956765212 978218827
355190718 425338922
544530219 227912122
646081635 149221446
484094787 91975735
341747794 606705927
934346315 821460404
233333838 284791629
779483487 350375700
282804417 475472995
719923777 394467738
158782041 130606055
120915955 210865887
117683535 85799143
824357539 90114764
920729589 781122751
920849945 128436660
58978026 465380163
356348782 705059661
467117963 840443570
797035396 808865757
447149496 583898065
482842514 680483335
721206048 262326001
883375389 4010464
737798996 455815519
250994556 896581038
586421574 224426866
959963279 704105109
162742363 784320817
646736227 83471951
417959921 567586171
64424965 476937948
885482688 420773747
34513962 352600650
261217316 684065713
13982760 560883167
120480131 496825274
93882855 841686179
611667629 977258244
698212998 201982979
433073762 949207554
98564016 872011690
26150773 911043649
428633152 188893136
547880819 75369378
124881441 965840741
495471903 189306406
295295042 380954590
610080154 182325358
586071594 723813824
866391071 600054354
284696990 986871202
949395982 378579845
828557381 561063611
208354442 379286732
763046590 641428204
181010639 714126960
365956247 207161413
477686962 794589399
248570903 25567780
869958777 373452345
843924875 217947033
415275105 139219916
598901623 25355258
174061629 37489570
601685437 40452699
637543924 886382427
27323901 439456260
117478626 708397636
519870 325833068
87684367 616082814
819777627 121211360
182726127 185733873
328372773 660413089
980323273 576943677
538497223 702798403
802912376 382422098
920745437 218187480
374158368 372163413
96059093 548219997
409652984 697744530
441189051 899713262
436643310 321029306
339169521 406638290
29426941 192205745
732471359 969627663
660804913 404765339
90839022 843531040
590499212 271728150
356460482 423338838
701188181 894957706
978653596 504100556
129896157 751915386
574804390 356570879
124078798 670863483
904790877 386248136
221124366 198496281
138477752 510284031
519525587 477647273
916922321 401468882
522369373 501910033
223612898 183174285
906675372 166968274
879221680 349690938
438696424 88198515
773029776 139884604
983156221 604199725
496501514 965568732
356115110 71305904
322139611 332710263
594685741 79446841
571474753 668326462
277943122 709952505
178610492 797468709
40116132 95532812
51453944 562485505
449959200 275066842
745659790 356634571
442035116 477397823
706325509 880731541
565596339 331871639
873132499 401268913
936071364 222150367
366837645 144702828
145972625 541493610
329929445 593174720
620940451 901404198
261501181 751399927
611356703 292628027
401384989 651472835
240677194 452838933
66474693 690636394
727905775 812134483
47270964 169940890
142048660 606112828
903188785 707644999
790500821 628837638
108913911 579088538
850988005 328267910
723791366 849476984
869761520 53720810
442651703 343218324
807641363 556669239
94618250 271514419
849297266 496003239
922987254 89974459
948842172 989461947
780610853 529264300
654112783 680398172
699205191 796161443
139027353 454910329
356322795 929528174
83747966 465236707
361133065 787252325
793504617 84924431
636729308 515782491
991161596 931897366
859000815 651319312
488566604 953619066
922833731 190380223
302138658 698337338
280354683 103497184
540315638 913481890
632761484 46944775
446396415 184483028
843106218 585423768
639393358 51945367
367468295 575657678
517182074 728601361
362910003 163203044
666042146 852155665
678985535 509720095
784053030 390502704
13555761 125135987
196638123 936389492
315516211 498776781
634726830 448387248
454790319 27558821
361869137 87551803
74503596 808265553
124551185 917609815
246205674 616460897
969555182 466190324
192118575 339253609
47308038 407544932
354973007 713350184
259700596 33958542
75586632 896269981
276977600 89142393
21405967 473615723
25531885 189438532
972392504 512775069
637825780 279699177
540333890 852211272
219767334 614837487
512993178 344318519
384963655 759198852
960779417 207035190
77905529 5414345
398805153 125213567
412959277 753778160
838563751 525176227
640253056 766666738
421446207 917230656
855809131 295368529
390846378 733857370
337323415 215755236
99148792 975149196
495454413 491999037
679876821 715221747
106836523 192869998
912056620 344316532
804585204 725352390
403868076 882490734
730766735 802673229
7704300 996242366
556451388 698784406
521418593 49220798
465451143 795381154
966451454 173776627
90749682 209814186
760150352 280589452
425569422 859299144
108255001 773540189
203814534 788131822
341278289 163167411
981001820 253334908
507483943 638103377
978687299 911352019
520594110 561970387
566541601 380814765
410729107 122992989
79599170 932147700
24730141 397566667
580045207 991181595
571343294 523311244
200995780 184009999
803900696 479081556
43309143 912155697
252621744 99640031
700287518 593900033
262807443 533805691
699751296 770291386
24425421 530954948
534159759 545019532
92925334 100701359
925834297 356170795
76210702 857949821
140834848 100940843
255516487 720880056
944638793 679376135