1000 100
821055 362864331
1534303 79550452
2549102 354381653
3084020 17154648
6162575 279487714
6865030 193977704
6996733 428924122
8784914 865246953
9116923 586150516
9469128 126564641
11300801 364470891
11573655 634807212
12483644 886823920
13440850 407612815
14431033 371405537
14436248 351605389
14756898 500912955
19053427 205239225
19724364 299553229
23486932 509620044
23652766 309386286
23679737 130444216
25867302 648579569
26005843 517208572
26719861 405229846
26952374 330838330
27233227 670431683
31838333 896642950
33402362 778000691
34130306 368969728
34277382 955028461
34563044 481912868
34717731 89380153
35075972 428281440
35117513 468877263
35538781 812529638
36258064 691460049
36267676 805263811
36781532 290081276
38336891 70439728
39513883 886886425
39724684 18966312
39865211 766223032
40246327 763032890
42324672 272096288
42804526 906822048
43577419 549830785
43796411 649277583
44023938 689040747
44034508 491467984
44408958 915021443
44420364 481678
44525822 666429811
44799185 209748338
47805895 19009826
47951348 38939372
48725077 935877669
50146164 678085075
50512490 134825076
52157948 44709937
55698822 779111520
56917421 26804311
57130516 308318916
57978260 166508598
58482298 667704954
58504688 241058801
62804346 558737169
65030449 202763693
65869836 407657660
66722945 945081515
68247135 90877324
68470193 756755865
69905499 816468449
71945786 139700260
73186078 549173790
73377415 31738833
73920910 942710683
74558095 819451405
75336877 613036767
75491748 228708738
75598920 661042958
76823781 863007915
78642646 658082976
81465617 66729898
81477558 268491091
82030262 384038745
82148739 44287842
83301910 408112542
83626392 147608055
84586710 625820930
85212086 538112733
87283027 314419076
91109125 252041081
91783749 764519595
92845794 707775738
93391296 388977370
93884248 959417807
94413059 598435815
95326291 551143001
98374616 146709741
99703470 374852834
100897421 946324833
101278469 288406732
102028898 822911331
103568505 543592205
104550022 152598870
104641700 743775194
105790860 361012914
105796883 524580770
106711293 773505048
107166642 155578173
110155745 296653990
110789703 302826341
111730361 721090700
112313958 294694756
112318211 187702495
114465190 280510223
114587846 998517421
114728890 794734066
117505963 967437136
117892133 334727116
118324109 530087943
119661921 174028349
121617015 201760962
129488487 77132733
129697871 904082492
130665608 333880272
130851858 288924495
131851216 353576567
133491436 97992067
136567187 1500393
137066684 58330343
137913606 202305411
138685552 213809956
139306356 280653052
142105227 769286606
142555136 214001884
143756798 309174781
145435882 101707566
145789168 127919900
145810617 725670772
146625544 190555392
147365588 806775514
147386797 263931196
147395552 842801583
149541991 838838194
150298498 813843984
150974194 986517613
151809489 809470949
151835750 654889134
152432237 738022929
154511989 402782532
155035874 641950437
155231796 429183520
157547949 353950164
158657138 213283624
161426037 674289261
161624081 445712459
161729233 564473477
163064386 666680533
163551270 112412083
165584745 786792963
165641991 36972032
165695056 658055386
167832775 880341983
168590051 132223796
168715057 357143386
169193589 369005083
170152449 670165646
170488808 115418969
170700510 997922137
171162966 795880527
173507921 612943953
174530340 651138565
174584849 229370103
175546711 471412354
176406926 61525292
176680234 639769438
176804470 36815843
178884587 21932437
179021843 464952087
180372767 260768413
180815214 929824511
181694189 350238905
181781807 315401344
182495418 471090319
184719488 415757027
186698747 906290168
187436219 264105159
188717578 952549399
189836807 799701081
191344538 53214892
193014150 829995201
193188478 922130602
194872774 452498143
195128096 850365958
196027667 799927606
197864035 231382225
198645116 106095400
199122711 746064264
199367270 403540835
199444976 479460522
200270338 188965787
200447987 322004875
202924351 224061305
203476156 987777128
206353674 244708562
206712744 4886970
208605311 605008668
211422402 185859279
211768165 176134173
213428097 20393365
213492048 89004004
213651648 80592824
214052606 92979709
217327572 920599280
218786411 155185631
219355926 953435283
219415386 858326697
222787049 847695985
224306019 902434317
227084139 771578080
227135861 137834636
227547107 297681429
230124521 109049571
233946911 209494709
234311734 852893380
234559012 457041323
236997576 700822217
237952050 511775547
241283552 64079269
241552830 874963799
242154495 473700508
244747363 224721713
245008079 930156852
247665311 621665297
250947663 145322541
251448556 870914920
252045976 940470701
253229793 543683108
255735454 338077375
256122052 330403141
257867244 422234622
258800433 362383279
261084754 956342669
261435514 18238786
261567432 993149001
261956975 749624103
262291637 306616386
262537030 220618092
264213755 379011686
265449148 554191315
267212402 213346174
267392410 833943014
268650029 659990110
269205693 841302095
274065086 829205336
274835271 278890341
274965598 704565489
278510559 844964618
279457193 696290263
279596228 136496563
279605142 318096913
280017570 600090823
281098014 979736952
282663679 402383917
284215633 654075749
284613740 965285664
284742754 173072811
286180764 250246725
286197665 32075463
288967552 732326654
289035814 164149078
289349566 306554368
289536908 923014855
289947204 642577698
291143734 215284048
291203916 84025464
292894043 153111333
293296314 244744352
293690188 463010535
293696964 884258395
294734785 129260890
295681234 56096095
296121638 152826971
296269514 220548202
298205334 932104976
298877901 536615066
299188803 613197664
300038300 441947131
300325594 423385253
301892479 267999073
302197931 912114080
302816448 841139064
304622784 391465389
305767095 415252249
307326329 840189239
307847882 427615966
308352339 211257709
309002472 928294904
309585496 341492021
310611493 566739007
311611302 358766945
313560273 108996490
313877070 277670944
314981215 95322176
318642130 141817782
319977321 148660527
320722583 17141871
320784109 197356188
321258655 137415632
323683665 899548314
324390328 176051984
326469318 700742303
329415107 476710086
331537391 163234899
331782870 546803683
332018846 806603691
332728315 668089825
332961306 735463990
333414819 895669308
333712825 859093942
334206358 330888993
334913296 120879602
334997043 470633317
335102558 640788938
339086143 909160888
341168241 246838667
341500462 159892761
342595785 209158276
344101871 660768908
344135614 508011993
344407701 368868363
345742258 905017494
346351115 126022329
347416958 221999367
347655521 29086301
350175580 63817030
351180363 779742221
351933735 235585812
352558881 737509929
353862531 578407148
354047102 702971275
354229723 974650965
356036945 834417148
356505696 756405624
356574997 685932009
357220425 527729137
358902485 605067093
360513931 427704041
360983499 542723089
361444804 782533732
363556622 224562987
365194568 751035351
365297290 931674532
365570233 775507453
366367550 943863908
368962197 390284778
369311558 390311282
370425901 294227807
370742898 383820895
370964432 775450720
372431648 859206147
373180637 818415108
373691066 905927019
374276357 152667275
376070401 617658385
376090619 907419317
377208920 491821389
378670977 753858129
381168659 835646220
382450261 8363539
383520873 830274495
383532165 906607274
383677713 612763029
385060585 578084626
385180580 523402475
385603985 204994086
387586068 370496515
388616907 65640312
391104927 329134580
393316443 730470245
393636753 979557601
395002538 894850659
396190529 264533869
396252197 760858524
397036499 825301869
397470266 15329984
398320330 134454751
400964060 720786199
401254309 147636251
401658017 768646613
402097302 678997576
405058085 572654513
405132623 912003857
406904855 26538423
407381458 132465815
408179459 949537629
408191515 35705512
409018051 301038549
409176883 3664945
409582522 488586401
410405317 877651953
410463761 817444715
412054435 114286703
412953900 750871830
414796250 656280365
417654170 866193936
419855471 534738718
422066527 276877289
422457312 338526804
423804785 944447017
425132997 716142845
425328646 376285789
425580809 859261328
427095002 939741555
427570070 753666626
428446966 701217351
430431363 823401919
430509254 745993085
430518390 722851606
430580071 675349648
431902300 184493812
432065699 222586923
434302356 714424852
436304678 46478263
436467964 328267509
437020248 728173109
439115746 218691790
440751449 207399501
440880192 414090687
441201167 582404517
441651926 467407432
443165582 368054646
444897566 767511550
445952260 631476829
446022217 847914363
447019283 498505070
447377615 959776150
447893681 373804687
448543579 165347283
449426152 688402946
450370997 354789917
451763813 379489603
453481242 446614962
454675335 244145427
455117154 327105886
456265723 778626260
457204416 641567979
457305715 120409367
458890509 115874263
459100862 385419123
459285854 286868807
461058453 364705176
467602479 61181755
467754730 453473699
467762689 672712963
470435578 907061170
471504912 564584178
471548849 754102971
475253006 769101136
475619017 87870105
475623658 494662804
475706504 494725991
476605001 992255698
476857196 394978833
476907927 233104498
477586799 667368999
478063335 133825058
479888801 106627316
480320125 480026125
480932926 319672783
482192530 421199436
482416620 499861424
485589918 791320733
486286807 276771846
487009272 539088722
488447697 123403462
490974954 785730443
491149906 439978951
491643338 946048679
492141626 610874700
492700133 534726391
492710156 169531874
493043715 321260980
493419772 79175020
493643896 154735155
494217773 313942396
494233334 88753750
494983847 312784099
497586895 343155781
500783928 834747531
501571354 837599070
501677502 647712643
502665944 388084841
504109174 244708443
504844100 260749584
506659937 899975601
507400645 167675021
508374416 278554123
508891897 285492644
509592669 505295079
509856612 440229844
510101141 857706257
512178144 873312201
513372921 834870323
514581644 579925780
515711169 339435954
519339593 591666973
519743790 786461367
519999539 178973015
520365036 460108171
520647116 756535990
522520266 979383335
522699955 863989342
522800427 15664651
523003164 921657244
523287002 118294350
523990586 21771545
524041567 540191990
525202852 422665548
525456448 76406921
526116900 942818864
526981609 52684515
527292044 856760375
527355752 7174218
528365916 156398205
528900015 647648703
529927949 553128512
530094432 707983766
531194331 337009552
531202834 779098953
531864210 186791234
534253379 397748872
534450322 723735082
534667056 55814547
535820631 945516936
537956115 419270860
538652283 117104322
539804138 725627271
539834241 327573075
540961437 127732772
540990150 148553219
541584217 388743008
543273978 455631960
544750259 290073831
547724308 8040780
547874347 850879789
548149023 782425663
548540685 583661693
548549595 122580782
550531476 171778897
551035982 297987877
553704402 295096292
554242069 753399282
556563826 766996229
557196433 163049755
557553404 779265070
559012084 564912145
560129756 547295957
562158353 551426980
564873227 787672833
567074366 283671737
567156743 197286175
567272822 691640379
567839653 890716949
568389227 525071951
568862142 883795607
569695475 439336651
570115173 923585722
572552201 372320488
573194887 934429894
574081625 646287925
574808164 684054095
574862264 388699854
577505199 225329286
578921260 32556238
579444593 650801356
580450041 208129793
581902188 888454792
582002610 107791070
583861480 707497017
584076609 344257459
585396644 540257230
585941496 534399777
587508753 60019253
587599609 17467595
589829492 110093873
590097623 795921226
591649426 304373872
592295777 962748003
593981394 915757276
594351247 802526332
599419863 189174576
600895173 663897418
601290320 610712271
601309131 745871311
601768422 533278160
604038023 793385347
605500752 181641053
606345525 113709265
608285867 314514749
608748261 671801028
612709427 569172654
612792532 444490754
614031140 890253944
614160127 711836408
614287773 926122046
616781602 354412374
618435498 395375382
620165926 444796094
620450701 786876764
622123264 98711735
623507949 385788867
624539573 824825831
625436372 339778476
626705750 96972417
628377938 826667706
630129442 272608251
631471925 952734117
632150562 862751236
632199022 43395663
633369204 541197493
636092549 997973268
636845731 802154502
637090354 982433637
638211292 547719299
638597515 218050455
640816479 275884350
642085105 522037240
642470691 43756295
643098491 372037923
643705599 88741594
644087976 200405397
644787655 12902808
646188470 733465215
647353816 896773370
647903199 985528285
647903581 203757506
648021839 313811911
648445641 429922610
650984116 940704006
651037033 498626498
651511135 796167401
651609578 893504268
654054770 128419417
655094036 200986891
656813218 409636395
656929220 127381124
657697006 204286133
657872118 324877507
658071875 120939171
658329497 443379338
658992241 942508299
659522879 998246470
660557847 537265854
661916638 758930308
661994733 974399712
663974751 535322530
664295986 996229306
666801768 360223177
669680806 386274510
670106222 430351898
670173060 973419307
671139322 885206055
673657432 343035650
674854266 662903460
675452200 664342906
676469170 381134941
677264954 926728128
678201728 530054763
679549776 534909537
679558661 840981410
680128665 603268059
681632740 434633549
682139460 552001136
683585870 200563484
684623056 660095293
685104682 627175517
686116417 195350155
688020055 18800234
688196212 2608997
688409192 411168354
688586056 205245034
688782983 814955035
689515025 183026148
689817231 67799639
690604303 965003032
691640335 466861621
691688192 414169311
692145417 337073641
692674931 416357237
692886300 98650287
694591396 751423376
695381463 663187964
696597536 758682804
697825092 444455414
698948574 124207813
699410909 706577702
702828377 117758685
703169347 661786476
706103777 270633824
706114941 594749490
706740846 125140300
707515810 525528548
708378992 920557781
709106680 106216095
710056418 842709808
712552327 399274536
712991561 640895407
713338277 819337503
713963483 490539021
715356070 717981555
716158916 199651339
716275714 786703896
720373810 493198395
720970050 965995000
721933915 433203738
724307718 118814246
724559180 880443748
726859488 486367577
729324378 619180708
730292179 264677527
731682547 744175370
734390422 944008496
734485469 155268480
734506965 745641453
735354813 147117822
735572546 256791433
736421235 116277277
737198752 927904864
737987571 892655082
738582021 507008870
741532741 148113917
741541399 262809178
743770019 785896905
747225212 604992314
747914598 609758516
749404008 565110009
749521791 996348009
750702546 821413231
751739654 563675373
752109212 623251088
752353012 964282864
753163847 743796960
754275084 528672741
756531363 167306534
759178906 613798740
759760082 217119583
759906158 984941294
761526079 19274997
762288429 199732450
762804527 445536816
763068513 904526702
763864485 577110252
765206729 273614008
766368283 680369292
767405188 961785309
767861606 542018862
771391875 313416010
772541786 481414688
772954258 614136395
773768528 241040785
775191774 171267041
775933646 732758411
776842802 5075159
776924931 559006752
777084916 955215639
777264417 651655907
777985319 477615673
778919493 660864922
779064774 264745820
780592371 357639729
780981833 503235129
781585326 437624304
782196885 302518132
782854806 699931120
784236856 161544757
784470318 112921291
784712763 695053559
785965553 124706194
787588540 981487519
790191234 396058627
790448239 458268368
792591329 310021627
793650346 295627901
794676631 405942313
796055270 776369599
796649521 650340356
798222539 496406504
798537620 779290878
799583340 915236055
801096460 815977209
803425977 806221965
805193443 950458362
805380871 472841216
806473730 137199387
806490943 162656047
811464665 299439814
812733969 364576886
813910114 796004896
815320495 69090082
816621229 59330
819345327 755319624
819618198 35372462
821616347 879043282
821756635 868894848
821900093 618793946
822027341 543202275
822238936 310777914
823286969 259270726
825130019 912016995
825468271 391455184
826324698 941615982
826928436 167790225
827016269 692465264
827936659 967213049
827979403 12216081
830347330 181105549
830609425 44604255
830891727 854337239
831098211 39695583
832035770 274504349
832685062 755997413
834913284 905474390
835348109 475824165
835471522 555214553
836804334 368740233
837778180 937186647
838106922 462660676
840676838 210555787
841472256 603856166
843841907 359857199
844264990 972225330
844900417 436704433
845814008 958842733
848268100 897654566
850914177 479790072
851746005 148302207
852375996 848458848
852687592 346920441
852981087 492279605
853567415 241604826
854588131 936299737
854761137 579629913
854807610 429025689
859268204 186153437
859675218 411889409
860223435 408769386
861072218 819762795
861401749 467344472
863347197 231449817
864568961 61286469
864590490 693872132
865261386 463186764
867539825 483825332
868202608 281706614
869673726 122386002
870640616 357397872
871927025 26715579
872587262 238505854
873791966 432749910
875859271 186757039
875987305 598290536
876715652 302979666
876724727 712949670
878353318 474663336
878358827 947603723
878640427 642786266
879108942 595506923
879164142 951493677
880364697 832817224
880391440 348668787
880977513 812831844
881817975 590718404
882457075 572979607
883369443 967395694
883760563 916673890
884711114 892263721
884739204 703684035
884932251 450358671
885304876 545095114
885758382 414084042
886723336 408770412
887918936 157675406
889072921 725679766
889629806 134733385
891154541 842772869
893372364 27355545
894261727 152711764
898589237 410113278
899485076 266168278
900047645 717615312
901147301 587199909
902203018 433526899
902452824 534674299
904793789 200893384
905252883 694179775
906299897 545047014
908891306 922759011
909152297 868067593
911735628 117434604
914624834 906593738
914680516 237860562
915923327 588019600
916617790 367529225
917420060 757623366
917875882 134796255
918782764 777566542
919069882 830090760
919870153 869106612
920265391 366500855
920464422 270025638
920629741 241929838
922631010 346621731
922632933 21258328
922795887 400466931
923145111 892684758
926347718 756841686
926482836 288300183
927250660 186382336
928152918 657591148
931324094 478136515
931380792 866200346
931404371 321463438
931998167 56385650
932706992 534621461
932724057 657393567
933200921 962356689
933275991 54471358
935991677 608084651
936667444 141624755
936870777 143597043
938117484 390238522
941860723 53452694
942673764 904771388
944240533 840723856
945287320 602571875
945535235 229218207
945564871 635857648
945833050 857087545
946964903 832321739
947862512 602464959
950856639 226426075
951370207 211399921
951559518 721552280
952706944 311511460
953016492 210987741
953661354 243998387
954249690 736435970
954307141 520928818
955331213 872732970
955408731 222008553
956675409 357748440
956995202 205551104
957161189 792325832
957434514 890484726
959038113 8662780
959085557 601220823
959435331 238923796
959783663 52429742
961001822 288942050
961040153 454620471
961835582 731376957
963301591 706749913
964332379 971720469
965380493 785882322
965405574 967218376
966887968 335374003
967093736 42934707
968857019 427318031
969056541 673809930
969144883 317353327
970730910 352622828
970784419 408158600
971226363 267012017
974272898 8401071
974677007 498698374
974971184 708425868
977180362 901228092
978006775 803510542
979580944 509242204
981286693 545442718
982617250 995421822
983035407 646766486
983810769 925212122
984388015 840181236
984554324 469258271
985491078 831303754
986351628 488340099
986727487 918511353
987582806 706982939
988278070 418446494
990434629 887382636
992550658 518598347
993161287 456056129
994183472 256072697
995270975 795064254
997102328 521518781
999728220 597749941
165 517 49128778
200 478 34724262
41 205 15667256
101 322 188607784
324 954 64052165
606 748 60399150
294 850 22602825
817 825 10630343
464 872 3006619
145 815 532825280
128 644 44956848
276 778 6371064
85 723 3985940
326 458 97010165
629 769 279465586
502 637 120071740
6 203 182983755
732 878 401445716
526 534 121331941
428 593 142814387
720 818 42644954
477 965 79870950
56 425 3741945
98 999 57584215
91 301 124772194
365 453 28776078
137 475 180003744
318 576 14140354
555 963 177501182
445 526 94760176
225 908 124820353
318 431 157298155
14 321 91407567
591 738 254065745
55 419 32839321
200 870 49341352
615 743 283681621
342 746 31455336
137 846 136113105
388 658 105603289
36 673 237404987
662 922 201428025
703 807 18553010
290 757 342397479
66 450 39750537
647 911 117676976
451 596 191044721
575 610 74595542
804 978 13674004
210 610 30852724
329 913 7290750
365 991 134669231
98 845 299770289
328 788 45688714
274 487 54889824
271 863 489230767
33 331 36104900
247 962 382232456
493 620 428015016
581 887 657346953
273 545 152864901
145 214 65252299
67 692 60639590
792 933 21195200
437 801 60287273
606 906 143791192
80 133 187026157
27 871 538305091
364 927 25547961
206 691 39998109
624 896 9844858
588 592 222292186
161 273 72762256
178 835 8273461
103 571 704348535
65 201 10061728
701 892 153455611
209 329 144552050
71 990 447379790
19 618 193076692
517 650 51979051
778 823 112062187
594 986 570624087
244 655 533084117
553 565 176758681
298 692 55809372
228 907 899301
482 752 260071987
515 657 9449128
140 758 522858731
13 238 369135161
206 604 116694463
543 705 111398548
731 956 204508921
538 769 45017780
314 473 439260534
860 912 59919182
747 993 6375027
541 770 54155174
516 872 267620633
545 520