6 1
7 0
8 1
9 1
10 2
11 2
12 5
13 5
14 8
15 10
16 15
17 18
18 27
19 33
20 47
21 57
22 78
23 96
24 129
25 159
26 208
27 258
28 330
29 407
30 517
31 635
32 798
33 978
34 1217
35 1482
36 1833
37 2225
38 2729
39 3303
40 4028
41 4856
42 5885
43 7070
44 8528
45 10211
46 12259
47 14628
48 17494
49 20800
50 24777
51 29378
52 34867
53 41217
54 48759
55 57477
56 67773
57 79680
58 93680
59 109849
60 128801
61 150657
62 176182
63 205589
64 239827
65 279221
66 324956
67 377511
68 438358
69 508198
70 588831
71 681272
72 787773
73 909676
74 1049818
75 1210035
76 1393833
77 1603655
78 1843930
79 2117859
80 2430958
81 2787466
82 3194231
83 3656797
84 4183709
85 4782140
86 5462750
87 6234797
88 7111538
89 8104843
90 9231259
91 10505865
92 11949310
93 13580789
94 15425880
95 17508962
96 19861826
97 22515176
98 25508437
99 28880378
100 32679757
101 36955202
102 41767148
103 47176386
104 53257632
105 60086792
106 67756105
107 76360123
108 86012599
109 96830961
110 108955326
111 122531368
112 137731277
113 154735410
114 173755355
115 195013674
116 218770048
117 245298850
118 274918167
119 307965556
120 344830494
121 385927372
122 431732232
123 482753340
124 539571659
125 602809387
126 673174933
127 751428714
128 838433437
129 935117073
130 1042528862
131 1161799614
132 1294204136
133 1441118072
134 1604088563
135 1784787256
136 1985089004
137 2207022391
138 2452857328
139 2725051934
140 3026351073
141 3359730139
142 3728504373
143 4136270348
144 4587028441
145 5085120483
146 5635368041
147 6243006899
148 6913841980
149 7654179585
150 8471001350
151 9371894153
152 10365246070
153 11460174829
154 12666747377
155 13995909395
156 15459731256
157 17071337960
158 18845187699
159 20797003165
160 22944084964
161 25305247879
162 27901174919
163 30754357971
164 33889499330
165 37333461200
166 41115718119
167 45268320246
168 49826404620
169 54828174530
170 60315479163
171 66333814078
172 72932977664
173 80167099814
174 88095386602
175 96782181821
176 106297815376
177 116718705667
178 128128323092
179 140617347514
180 154284762833
181 169238078149
182 185594575856
183 203481612094
184 223038035523
185 244414586390
186 267775514420
187 293299090922
188 321179457728
189 351627277046
190 384871842020
191 421161893493
192 460768031071
193 503983727053
194 551128084545
195 602547086677
196 658616748597
197 719744651078
198 786373544528
199 858983212647
200 938094603046
201 1024272079980
202 1118128153580
203 1220326196789
204 1331585864745
205 1452686349169
206 1584472595151
207 1727859192071
208 1883837496681
209 2053480275361
210 2237949871472
211 2438503720540
212 2656503720877
213 2893422770034
214 3150855514054
215 3430526079500
216 3734300407532
217 4064195372098
218 4422392943183
219 4811250918368
220 5233319175846
221 5691352295322
222 6188328209759
223 6727463010105
224 7312232360298
225 7946388841255
226 8633986523614
227 9379401263259
228 10187358906535
229 11062958989003
230 12011707117252
231 13039542611089
232 14152875665669
233 15358619560411
234 16664233305139
235 18077759118891
236 19607871369663
237 21263920140055
238 23055987368613
239 24994937451805
240 27092481636934
241 29361236718091
242 31814798903259
243 34467811832948
244 37336051279203
245 40436503912919
246 43787464412004
247 47408626571022
248 51321194625005
249 55547988563201
250 60113571693144
251 65044372289166
252 70368829740259
253 76117534938206
254 82323397687147
255 89021808600283
256 96250830802378
257 104051386506428
258 112467476481337
259 121546394898197
260 131338980539027
261 141899864030352
262 153287755271437
263 165565727786496
264 178801547499148
265 193067999535765
266 208443264211143
267 225011292401906
268 242862235354516
269 262092875609176
270 282807118211253
271 305116485072950
272 329140676210998
273 355008136577559
274 382856697076093
275 412834224143858
276 445099351661020
277 479822224942209
278 517185336180338
279 557384376125790
280 600629187369369
281 647144738830151
282 697172213150690
283 750970121087429
284 808815541539037
285 871005395292982
286 937857858599981
287 1009713818401659
288 1086938483232911
289 1169923044934010
290 1259086513859155
291 1354877615524506
292 1457776880599037
293 1568298808750582
294 1686994248031360
295 1814452862402946
296 1951305839728147
297 2098228704359059
298 2255944398069640
299 2425226484597049
300 2606902653735548
301 2801858370833512
302 3011040860919231
303 3235463263191164
304 3476209159370015
305 3734437301186186
306 4011386755612630
307 4308382282102162
308 4626840176893086
309 4968274386869546
310 5334303145660143
311 5726655922327122
312 6147180954139476
313 6597853140888177
314 7080782592781800
315 7598223595651993
316 8152584307557793
317 8746436936327281
318 9382528735715614
319 10063793554828063
320 10793364304051525
321 11574586056441408
322 12411030175280297
323 13306509170624504
324 14265092704892968
325 15291124433490325
326 16389240132476995
327 17564386781415797
328 18821843087889622
329 20167241103573741
330 21606589455282563
331 23146297821847136
332 24793203220484456
333 26554597713611492
334 28438258142984081
335 30452477482044265
336 32606098459728882
337 34908549025899231
338 37369880362067697
339 40000806986110737
340 42812749709087263
341 45817880971176375
342 49029173373505411
343 52460450910745963
344 56126443785100364
345 60042846283751977
346 64226378669462303
347 68694852543924347
348 73467240707764095
349 78563750954376025
350 84005904902330700
351 89816621280892083
352 96020304860789171
353 102642940423095467
354 109712193052745991
355 117257514128177808
356 125310254396684441
357 133903783486043007
358 143073617353665011
359 152857553004583354
360 163295812100356315
361 174431192772460413
362 186309231393867024
363 198978373606304723
364 212490156499737622
365 226899401228583736
366 242264418115846053
367 258647223519715895
368 276113770682778686
369 294734193831283668
370 314583067928473916
371 335739683347416061
372 358288338066847908
373 382318646658405113
374 407925868886959152
375 435211257200931835
376 464282426171595869
377 495253743174931042
378 528246743633017306
379 563390570133417007
380 600822439025653295
381 640688133847293604
382 683142529486456355
383 728350146479133616
384 776485739683542104
385 827734920788514171
386 882294819265384858
387 940374781292961996
388 1002197111666188184
389 1067997858308796895
390 1138027644837815092
391 1212552550910464316
392 1291855046280537332
393 1376234978426346230
394 1466010620201144048
395 1561519777526246931
396 1663120964150185690
397 1771194643680299998
398 1886144546538382722
399 2008399062264492082
400 2138412715508276021
401 2276667726387557689
402 2423675664306147911
403 2579979196207737407
404 2746153939183638206
405 2922810418754569330
406 3110596143649275565
407 3310197798797885451
408 3522343568353972764
409 3747805590920541888
410 3987402559883050711
411 4242002471547374377
412 4512525535181096405
413 4799947248255688814
414 5105301652298651725
415 5429684773336941221
416 5774258263781973278
417 6140253250515024066
418 6528974407605206516
419 6941804259304988282
420 7380207733491782685
421 7845736972205459045
422 8340036421360107163
423 8864848207416880286
424 9422017825195084498
425 10013500145895759986
426 10641365771821149697
427 11307807748317832604
428 12015148661964961654
429 12765848137172910253
430 13562510763004894517
431 14407894464234374342
432 15304919351518375509
433 16256677066778608131
434 17266440662047861994
435 18337675030208647400
436 19474047929596926392
437 20679441623523303293
438 21957965180771477826
439 23313967461070430114
440 24752050836101921911
441 26277085673337822688
442 27894225638223592726
443 29608923845699077280
444 31426949922025755157
445 33354408012048363516
446 35397755798865856206
447 37563824575664204813
448 39859840443298359517
449 42293446678547277879
450 44872727353908001344
451 47606232259627751991
452 50503003216859758546
453 53572601839083391515
454 56825138839506948060
455 60271304948782316922
456 63922403550475277800
457 67790385106632970657
458 71887883491608927301
459 76228254315411316866
460 80825615366537142174
461 85694889265500487007
462 90851848472015058834
463 96313162748103703147
464 102096449234416591522
465 108220325254336510982
466 114704464018928586561
467 121569653360998939014
468 128837857688695298497
469 136532283302123728056
470 144677447282559942714
471 153299250114621849190
472 162425052272071542809
473 172083754946377305940
474 182305885171930047119
475 193123685547872806193
476 204571208836027677554
477 216684417657984695617
478 229501289599022891478
479 243061927967562493662
480 257408678548860738404
481 272586252630069391574
482 288641856669564906846
483 305625328919163141400
484 323589283409793985653
485 342589261644147935566
486 362683892448347368075
487 383935060364809322864
488 406408083084035831058
489 430171898340295400018
490 455299260819237792441
491 481866949549784357280
492 509955986383725096212
493 539651866087791521708
494 571044798712632944527
495 604229964821453755742
496 639307784309897522761
497 676384199464073478723
498 715570973062242145842
499 756986002237964253698
500 800753648991626383561
501 847005088146516965898
502 895878673725961211792
503 947520324634297335005
504 1002083930716811945339
505 1059731780177092281760
506 1120635009535450124849
507 1184974077212535492642
508 1252939262041238512996
509 1324731187907669350046
510 1400561375955745060166
511 1480652825684962361939
512 1565240626520507972514
513 1654572601327409971688
514 1748909983606994513546
515 1848528130004176106979
516 1953717270038873317535
517 2064783294863070864752
518 2182048587149358608799
519 2305852894103243885444
520 2436554245916832589457
521 2574529921866537800885
522 2720177466605294578800
523 2873915759083828843599
524 3036186136907563758756
525 3207453578819272279839
526 3388207948395652155337
527 3578965301929543838771
528 3780269263895547161916
529 3992692473280996454724
530 4216838104520380325412
531 4453341466656867052495
532 4702871684843102418401
533 4966133468181241684087
534 5243868968425506088725
535 5536859733961530430930
536 5845928764037606174018
537 6171942668118130856154
538 6515813935830826029700
539 6878503322879959687575
540 7261022358942573670207
541 7664435983472247238283
542 8089865316026612288859
543 8538490567650752020393
544 9011554100590887674247
545 9510363643538839837741
546 10036295670404547640391
547 10590798950552154790450
548 11175398279290810891680
549 11791698397363885015490
550 12441388109099438776913
551 13126244608854162727881
552 13848138026370665441376
553 14609036201656935751684
554 15411009701058515489697
555 16256237086205468982415
556 17147010448657934351239
557 18085741223111663197346
558 19074966293253029115158
559 20117354404420521496161
560 21215712898551191731329
561 22372994786992179432565
562 23592306178179858465574
563 24876914077329677777657
564 26230254576811322402500
565 27655941456068472926187
566 29157775211592086896906
567 30739752537690655371853
568 32406076280578322525808
569 34161165888592621671440
570 36009668383269276033032
571 37956469876355846192333
572 40006707659911394690133
573 42165782897064978816042
574 44439373943233265898510
575 46833450328103247267236
576 49354287431089011558595
577 52008481883566895161364
578 54802967733786462423726
579 57745033411050349625047
580 60842339528555200084923
581 64102937565093455227201
582 67535289468838215408534
583 71148288227365794775540
584 74951279451335086290515
585 78954084020314293501471
586 83167021842772496909460
587 87600936783479699961662
588 92267222815370398480736
589 97177851454323881139642
590 102345400539434448410966
591 107783084422933789015395
592 113504785638382478255159
593 119525088117548378616652
594 125859312031207563652931
595 132523550331138892428564
596 139534707075795255371371
597 146910537624429810375073
598 154669690790095089113107
599 162831753044515633553978
600 171417294873938478314169
601 180447919387966446809323
602 189946313289986714695753
603 199936300321058848566224
604 210442897296281022503725
605 221492372856292568066777
606 233112309064319359786762
607 245331665983235768271347
608 258180849375510205165379
609 271691781673440121085172
610 285897976376176059697795
611 300834616035093000934033
612 316538633998921664840652
613 333048800095683628068505
614 350405810439154878905163
615 368652381553843849471947
616 387833349024048419348834
617 407995770879511323552948
618 429189035942746995434615
619 451464977370830593786989
620 474877991638053103338283
621 499485163214402516721166
622 525346395209595552424882
623 552524546261861793301821
624 581085573966697500665664
625 611098685151295747161259
626 642636493317734325775844
627 675775183589603206968328
628 710594685515605501890607
629 747178854096485541543942
630 785615659422095320697338
631 825997385319567953492839
632 868420837435769357864040
633 912987561192823759280189
634 959804070079607716434217
635 1008982084759340068058154
636 1060638783499555558137084
637 1114897064449745248928697
638 1171885820320347701574186
639 1231740226037701260241961
640 1294602039980404023447880
641 1360619919425569465867400
642 1429949750866948926807498
643 1502754995892249416196774
644 1579207053343335768561039
645 1659485638510898191503322
646 1743779180154654497417072
647 1832285236170822232850412
648 1925210928771483748911323
649 2022773400074167837724426
650 2125200289046554863947481
651 2232730230788231726913608
652 2345613379182023286422709
653 2464111953988075272391860
654 2588500813508830241117028
655 2719068053997653584866446
656 2856115637043579220457445
657 2999960046213595403016246
658 3150932974298762546978694
659 3309382042564142811008172
660 3475671553472999761097433
661 3650183278414588995659514
662 3833317282041433780276321
663 4025492784886493495342165
664 4227149066013830149483954
665 4438746407527062544028215
666 4660767082850294616201259
667 4893716390773625016406016
668 5138123737353566737568576
669 5394543767843477989689453
670 5663557550935831326427825
671 5945773817690942986687243
672 6241830257642751877895299
673 6552394874673785205247574
674 6878167405377458504888574
675 7219880802736952370276813
676 7578302788086832868681198
677 7954237474445088942949009
678 8348527064452044148480057
679 8762053626285459099566992
680 9195740951082811527712733
681 9650556495546976031249920
682 10127513413587197978128433
683 10627672681005981112970372
684 11152145317433393444489181
685 11702094709883722366954793
686 12278739042516822836122400
687 12883353837375947064399702
688 13517274611099212816521600
689 14181899652808762873479098
690 14878692928626542471911012
691 15609187118491525224425309
692 16374986791219281013731770
693 17177771723991383887527652
694 18019300372751236612137263
695 18901413500252034270122061
696 19826037968816666167009654
697 20795190705163042247923701
698 21810982844989557675592323
699 22875624065335810372000589
700 23991427113104400119861493
701 25160812538479114758958757
702 26386313642377543490415089
703 27670581647457275568040224
704 29016391102632348484597402
705 30426645531472155667291833
706 31904383335330285388509713
707 33452783962503763137976908
708 35075174355239424720331974
709 36775035686897889759825929
710 38556010402146366548962244
711 40421909573589572524458551
712 42376720588857132639634751
713 44424615182752058091562577
714 46569957829726435271989246
715 48817314512589089425136928
716 51171461884068447439957687
717 53637396838549420080510696
718 56220346512083378315525577
719 58925778729527812976936016
720 61759412918519587645832135
721 64727231510810507903566715
722 67835491852414034342528938
723 71090738644909916087514951
724 74499816941252608327819844
725 78069885720406757428745239
726 81808432066217826361931832
727 85723285976989696329045625
728 89822635833418857931385875
729 94115044553692365688384471
730 98609466465835393239237552
731 103315264928653670677796147
732 108242230734004194813525001
733 113400601324497700690589438
734 118801080862243216186420144
735 124454861185735282025976561
736 130373643693620032133050664
737 136569662195697065198420163
738 143055706773289325328033193
739 149845148692875601731928412
740 156951966418807025393934896
741 164390772772845109210415661
742 172176843290349918975967163
743 180326145825030046825307356
744 188855371456435230267094771
745 197781966756636701020835899
746 207124167475002663146637347
747 216901033702437130966998843
748 227132486579122078492126917
749 237839346612476998435879871
750 249043373674948708827105740
751 260767308754149829629874048
752 273034917531009186815978456
753 285871035864754057729117076
754 299301617266955759869371662
755 313353782450299085257414323
756 328055871041436792793454716
757 343437495551014756406519197
758 359529597697967420358538981
759 376364507189227939933148854
760 393976003060351006129150514
761 412399377686938450604245669
762 431671503581479302543868499
763 451830903094984707778086757
764 472917821147918382335973476
765 494974301120100345514246481
766 518044264034813889475777391
767 542173591177965465718143707
768 567410210299167331205455711
769 593804185547712321694235401
770 621407811302937195124445541
771 650275710065090528988259929
772 680464934579897306328411864
773 712035074377195413089842085
774 745048366911690116471325756
775 779569813501666342174422404
776 815667300269813473569643417
777 853411724298772789248248343
778 892877125223030021807727394
779 934140822487947732677122840
780 977283558516499794947341451
781 1022389648034219004487265264
782 1069547133813454158557086071
783 1118847949108822772534774699
784 1170388087067216236829345010
785 1224267777407415023339905710
786 1280591670676800594487507275
787 1339469030405338033535654508
788 1401013933490469925659910439
789 1465345479160317693342478067
790 1532588006877176053375347823
791 1602871323558198662455239530
792 1676330940505977865945366553
793 1753108320457886206517624837
794 1833351135180167517401744963
795 1917213534050285901966479510
796 2004856424089584429467477642
797 2096447761927293383644299637
798 2192162858197011578599421138
799 2292184694887360659470710847
800 2396704256190262375135939952
801 2505920873412584271093445595
802 2620042584540452158498595094
803 2739286509069683476658831661
804 2863879238741298874012393990
805 2994057244847238058869245829
806 3130067302799018837037153003
807 3272166934680424939191237383
808 3420624870535202962634001128
809 3575721529171451707489693057
810 3737749519296749820238869325
811 3907014161831319563460868243
812 4083834034281556091900169609
813 4268541538092260661548605847
814 4461483489933833849991406022
815 4663021737919675988027619996
816 4873533803790080327394821884
817 5093413552141120667579892213
818 5323071887821447550356475075
819 5562937482665610901102556914
820 5813457532780587115919962527
821 6075098547651663473166550772
822 6348347172385836161309006735
823 6633711044464430438844663687
824 6931719686432917324048836510
825 7242925436013861502042634491
826 7567904415189808135552541744
827 7907257539865641763956305948
828 8261611571785802713975472412
829 8631620214449622791029384972
830 9017965254839275262470363371
831 9421357752848277709607812813
832 9842539280375534298273006388
833 10282283212129364330209376300
834 10741396070269294835809629075
835 11220718925099357305175892613
836 11721128854116747848465378957
837 12243540461812698263099498834
838 12788907462719858425295026607
839 13358224330301069860644018750
840 13952528014379785696093326287
841 14572899729921173103248270697
842 15220466820086867354517609412
843 15896404696603987529266502323
844 16601938860612200063563408645
845 17338347007279827894006848967
846 18106961217613161865500615293
847 18909170241020680055437826597
848 19746421872337820327184409460
849 20620225427166665139269673472
850 21532154319540478910827047846
851 22483848746083809230229684812
852 23477018481007014732622596236
853 24513445786447873573741634277
854 25594988442854649930960022232
855 26723582904292845775224782740
856 27901247583754241034050370318
857 29130086273749854022669685635
858 30412291707680647480279147675
859 31750149267699221436634627164
860 33146040845005001763086269444
861 34602448858752539226696606096
862 36121960440000230681492928043
863 37707271787382975109333649934
864 39361192701459864274140572367
865 41086651304964818952927857416
866 42886698956477134265652918887
867 44764515365327952404721269122
868 46723413915870897422209339215
869 48766847209568166137374388313
870 50898412833680580163108725577
871 53121859365699066531682390160
872 55441092623019213386858265528
873 57860182167737459187759557711
874 60383368076840748028829731521
875 63015067988468550923879997724
876 65759884435350814795142303795
877 68622612476965000758057104407
878 71608247642413893622676488099
879 74721994196500559052813845699
880 77969273741971866075304200466
881 81355734171414542773540103871
882 84887258982822164111947797283
883 88569976973404851648609022208
884 92410272326790377063470694977
885 96414795109362778415783022159
886 100590472192107321693727762508
887 104944518614975546960641558721
888 109484449411456261429170474224
889 114218091911734458861787380990
890 119153598543545532118750985852
891 124299460150583480973536704801
892 129664519849104632369423615529
893 135257987444179260957155508367
894 141089454427888224575314607453
895 147168909582636785246153843023
896 153506755213669254297987893540
897 160113824035812349280092102494
898 167001396740458560563227475042
899 174181220269819660835346128398
900 181665526826541443793997906910
901 189467053647870007455509974288
902 197599063574704424149440468576
903 206075366447056515546737272291
904 214910341358673044528606775698
905 224118959804854892086186512159
906 233716809758839438511206162558
907 243720120713492253402538582892
908 254145789726490433661031277550
909 265011408508668246371527286743
910 276335291596744653218829621210
911 288136505653257443544514556089
912 300434899938199028484885883448
913 313251137998579973767017064201
914 326606730623947465765861307653
915 340524070117752537179807424862
916 355026465936401889225211541045
917 370138181749842859509987773792
918 385884473979623860166814645088
919 402291631872542675192036509609
920 419387019170252244972587491667
921 437199117437533111677936173387
922 455757571114374990052369383185
923 475093234359532006389947055594
924 495238219755839035526400058851
925 516225948950295218805924969584
926 538091205304747801422976876669
927 560870188635939763187090188534
928 584600572126731617528840112431
929 609321561493466024440838765116
930 635073956497727473428826844236
931 661900214894152981991516616483
932 689844518909488215494996346395
933 718952844351751348192038823086
934 749273032452179807103629271831
935 780854864546587405911729678429
936 813750139706867544794494631774
937 848012755437636723374969778373
938 883698791557438698091510592813
939 920866597388517787475906965244
940 959576882383938098026191402746
941 999892810325768374584675500383
942 1041880097233188730758262152269
943 1085607113124700257292344714808
944 1131144987784151401178417728897
945 1178567720686030648541790194072
946 1227952295241434452439233671588
947 1279378797532297157212180358318
948 1332930539707888027850454817568
949 1388694188224234093538375131951
950 1446759897114039689000155910271
951 1507221446481839109558924648607
952 1570176386426562270291608720517
953 1635726186601409572918235764227
954 1703976391628947247655365306132
955 1775036782597643288994336636353
956 1849021544874694060269760949689
957 1926049442478937912480759441951
958 2006243999266943550761648541971
959 2089733687194992805063270850494
960 2176652121929680296450045735280
961 2267138266090221900305579236964
962 2361336640416331935592258446943
963 2459397543166691605660067213285
964 2561477278064622188877031321445
965 2667738391119592109931066176507
966 2778349916665662992644563193729
967 2893487632970912768760986779840
968 3013334327785301553010421655395
969 3138080074208365396441585671577
970 3267922517272573955520107972357
971 3403067171653168164382233864887
972 3543727730930845155154245287838
973 3690126388849778098871421268706
974 3842494173030192679651789201186
975 4001071291612068362522221234212
976 4166107493324538314674877288868
977 4337862441494226295731329298631
978 4516606102525131541963462317358
979 4702619149402753930630370609311
980 4896193380795993835163212086180
981 5097632156351965252650258473451
982 5307250848801282299494849800008
983 5525377313514620195437956516310
984 5752352376175470856559158974949
985 5988530339259013451417090856710
986 6234279508032963570447403594127
987 6489982736823155481375717628552
988 6756037996314515692148484230951
989 7032858962687008515512153285855
990 7320875629416144715818971316743
991 7620534942598749887057796841912
992 7932301460696963176643361321227
993 8256658039626888218824531676303
994 8594106544153024165045215710955
995 8945168586585576161798300863037
996 9310386293815063561213892255688
997 9690323103757323173915323146326
998 10085564592322130844302102587349
999 10496719332060252303620809380523
1000 10924419783686875619873315567606