1 0
2 1
3 18
4 137
5 650
6 2350
7 6860
8 17609
9 39870
10 83976
11 162382
12 301070
13 522886
14 885284
15 1424468
16 2254537
17 3419448
18 5143987
19 7448874
20 10750712
21 15015872
22 20948610
23 28373444
24 38539022
25 50863150
26 67454492
27 87209316
28 113326308
29 143748766
30 183759900
31 229271536
32 288585417
33 355315792
34 441113706
35 536167960
36 658477019
37 791098554
38 960911606
39 1144114132
40 1376100984
41 1622951708
42 1937057120
43 2265154430
44 2681596450
45 3115375670
46 3660186444
47 4221858472
48 4933011214
49 5651864820
50 6561362101
51 7481840676
52 8634717644
53 9789258258
54 11250022204
55 12687121932
56 14505799396
57 16298259792
58 18543615204
59 20738760662
60 23522723420
61 26189521742
62 29576057936
63 32839892300
64 36938970825
65 40852420336
66 45835774464
67 50505927538
68 56466018042
69 62081314496
70 69165710184
71 75792665004
72 84285153563
73 92061651084
74 102051764120
75 111288855718
76 123004196182
77 133737859328
78 147590784572
79 160032570776
80 176141000312
81 190727142012
82 209360839254
83 226133753482
84 247958413920
85 267150988548
86 292205000978
87 314522739028
88 343244605218
89 368594451588
90 401883556812
91 430634706264
92 468532347788
93 501646657024
94 544619846712
95 581955189124
96 631425566478
97 673319029712
98 729090679773
99 777076470814
100 839905353837
101 893446118170
102 965157584796
103 1024894878748
104 1105244541772
105 1173136276672
106 1262814464160
107 1338151220190
108 1440090235388
109 1523365923222
110 1636638897060
111 1730924547924
112 1856742530788
113 1960504555016
114 2102475705248
115 2216711595144
116 2373726714388
117 2502179237362
118 2675300330778
119 2816099593752
120 3010910279772
121 3164582094146
122 3378448531700
123 3551019577700
124 3785964955472
125 3973693831900
126 4236346367108
127 4440632150976
128 4728188565193
129 4956159323984
130 5269962500292
131 5517188497106
132 5867334782848
133 6134522549056
134 6515264953166
135 6813328307816
136 7227654087546
137 7548535864684
138 8008489910688
139 8354536381198
140 8853747461608
141 9237428205568
142 9777254143428
143 10189926334028
144 10788500138779
145 11230531946016
146 11875953378854
147 12366282350034
148 13063417361800
149 13586970484130
150 14356262828650
151 14916172053380
152 15744545060950
153 16362791454516
154 17252184311520
155 17912087386336
156 18892765093244
157 19593693947230
158 20644202123144
159 21418899748308
160 22546048630392
161 23366863038016
162 24603801871429
163 25476043640706
164 26799810996518
165 27759425808192
166 29171254770966
167 30187979849468
168 31738692700768
169 32811470363490
170 34462478141856
171 35644305071418
172 37404505995186
173 38649286010614
174 40573434017532
175 41888150055460
176 43935310409506
177 45376412025296
178 47548684959822
179 49067052507546
180 51444211506044
181 53035757677266
182 55551877864168
183 57302677657172
184 59972169778572
185 61805398554904
186 64712419590272
187 66636169266204
188 69715563172024
189 71820849154304
190 75072220261356
191 77277368425888
192 80822473557774
193 83122752656800
194 86858155745522
195 89385100680232
196 93329259937701
197 95958253910442
198 100242865743330
199 102988868927340
200 107507937304109
201 110506974866896
202 115254550274232
203 118383601062104
204 123547653932892
205 126794769938508
206 132211440451220
207 135771869308868
208 141471303155532
209 145158602784848
210 151334580904320
211 155165777109322
212 161650042010640
213 165834357471168
214 172621508629554
215 176967506678380
216 184331638831100
217 188815402216704
218 196514205390668
219 201430899574116
220 209502467456100
221 214567863839868
222 223289268100508
223 228535038767504
224 237663045557988
225 243388786256920
226 252905089039962
227 258821144993506
228 269133190260256
229 275211850297306
230 285955797306744
231 292618444457408
232 303837164970900
233 310677785592252
234 322781123283584
235 329836982469072
236 342459182948666
237 350151273732608
238 363276849284424
239 371196660548168
240 385396519299164
241 393493943125448
242 408231091917727
243 417120269514102
244 432467603622180
245 441557667622770
246 458081527453116
247 467409391266692
248 484603745746768
249 494780662910800
250 512606506283976
251 523039880738550
252 542285177225796
253 552920159324544
254 572841549524288
255 584526374087976
256 605208138741449
257 617092995954560
258 639344555020160
259 651504815041816
260 674596054950244
261 687861386295562
262 711717318374766
263 725285497013836
264 751019210242944
265 764795687435208
266 791353411188064
267 806484672764004
268 834004422639662
269 849346133127174
270 878919354283704
271 894548290271544
272 925139729500026
273 942228750915648
274 973761129115590
275 991181510190682
276 1025148792948896
277 1042742650050146
278 1077735195860162
279 1097101483198192
280 1133280214417896
281 1152823957484836
282 1191628241425344
283 1211501071426342
284 1251564326244996
285 1273317969361792
286 1314500500017348
287 1336572614218072
288 1380928021347099
289 1403148557879976
290 1448738624109204
291 1473222053437988
292 1520214097645558
293 1544870557507130
294 1595250426458190
295 1620236548976412
296 1672118217106696
297 1699466259982432
298 1752719195760720
299 1780397924032840
300 1837712934892170
301 1865454885324800
302 1924186198328972
303 1954860125101396
304 2015301779263574
305 2046082723153792
306 2110800101352462
307 2141841761909850
308 2208413333857760
309 2242470014369728
310 2310659276591136
311 2344992602842292
312 2418275080542076
313 2452613512976276
314 2527586523062564
315 2565649595095000
316 2642617908770568
317 2680609728684238
318 2763038071700316
319 2801260888326732
320 2885894229409400
321 2927874891826512
322 3014325336089856
323 3056584537366356
324 3149477371651853
325 3191595519289086
326 3286409633981822
327 3333124663320276
328 3430377435537318
329 3476886925697408
330 3580965933956064
331 3627560884787246
332 3734146749583222
333 3785532802937958
334 3894249405238836
335 3945826290330388
336 4062552686348896
337 4113656838689944
338 4232679681719217
339 4289583992347172
340 4411464358718592
341 4467858694420736
342 4598115359405942
343 4654554518889240
344 4787779038342322
345 4850164997772096
346 4985757900546924
347 5048066617014662
348 5193714083129404
349 5255290679577470
350 5403571362572684
351 5472266022583528
352 5623719738814242
353 5691695944602448
354 5853557157013824
355 5921377978745304
356 6086600275653534
357 6161625941556864
358 6329649779208774
359 6404421310799772
360 6584862195112188
361 6658389055247526
362 6841612746297056
363 6924105653903522
364 7111071008124776
365 7192408805450284
366 7392045424130684
367 7472762913016328
368 7676437767148940
369 7766081474118296
370 7972896419965020
371 8061885924129432
372 8283691361719424
373 8371062348146674
374 8596065841885764
375 8694442139636968
376 8923596315456696
377 9020034784018328
378 9264889547936576
379 9360374476252086
380 9609826156421932
381 9716103183206400
382 9968780533907424
383 10074190795326272
384 10345276623783694
385 10448404295694528
386 10722835099916258
387 10839122746779470
388 11118517262670594
389 11232229363255498
390 11530677995504472
391 11642762995616520
392 11946150932504037
393 12071608472133584
394 12378614762092392
395 12502704944921776
396 12831863900691970
397 12952461238024902
398 13285564099507460
399 13422335379811648
400 13761016035003437
401 13894066151490680
402 14255399766250976
403 14386464681403360
404 14753475890492584
405 14900749055552162
406 15271484545401576
407 15416281816047116
408 15814107195295068
409 15954452670575332
410 16356525330751704
411 16516196518212964
412 16924089282469460
413 17079283319532928
414 17514571150055148
415 17666925996196932
416 18108326814719820
417 18279725650402384
418 18725459768382912
419 18893695627345154
420 19371999502952320
421 19534100815758074
422 20016385256496470
423 20202259759762984
424 20691215177488272
425 20871171386188548
426 21392632123802208
427 21568225050590168
428 22096891266828498
429 22295558871552512
430 22828808371529028
431 23022879745251816
432 23594449869547516
433 23781214405067112
434 24357186896203264
435 24572403953199528
436 25155341667583996
437 25362310395971392
438 25984586055953468
439 26186074289813108
440 26816328533754468
441 27045065210857650
442 27679254446143944
443 27902610551305750
444 28582757254177756
445 28796810582994588
446 29481020012097584
447 29728291478819540
448 30420869844311780
449 30657952073444640
450 31397153439066187
451 31626750273181980
452 32373811914656234
453 32636584514768576
454 33387927715859358
455 33643767553054064
456 34449064665594400
457 34692225003382220
458 35502328700361464
459 35785424981404104
460 36604558780656888
461 36874422859203622
462 37747779347835456
463 38008934134267096
464 38891157274292116
465 39191647268871424
466 40077434354049846
467 40367970695661258
468 41318485974511088
469 41593855651595712
470 42548970751592112
471 42871002426197332
472 43834796171182650
473 44141466894640016
474 45169514325311552
475 45465249719595374
476 46502252823213768
477 46843143613842366
478 47884369224365592
479 48213354363459856
480 49330754488232028
481 49640288341710416
482 50760718677180314
483 51126696402523264
484 52256744363519239
485 52603723108517812
486 53808514782219946
487 54140402785852764
488 55355879469730468
489 55741583563818192
490 56960939138204448
491 57330957988371998
492 58637986550944892
493 58985761429913004
494 60295811488481548
495 60709877014225164
496 62029279702286160
497 62418596963330496
498 63826705531503264
499 64198158889545850
500 65617606515900712
501 66051299994470336
502 67472144631086202
503 67888255566883668
504 69412535543803972
505 69801372097845720
506 71326700569073952
507 71791497242238246
508 73328158989695296
509 73763791280126702
510 75403902274685496
511 75816823048985176
512 77466641778079433
513 77954095292114400
514 79604996495112834
515 80070938007339448
516 81841059221940480
517 82272099062669952
518 84044121157819240
519 84564637884422356
520 86348335906268772
521 86832602377052844
522 88734118850590728
523 89192959825526094
524 91105333960699982
525 91651272418876672
526 93561829132976292
527 94079079940378080
528 96130459288230784
529 96606969398296060
530 98658643697900460
531 99238233941594534
532 101299371175859808
533 101837850500917636
534 104036522806295676
535 104544403024842540
536 106752616625760046
537 107358710989746768
538 109565651192870556
539 110138881028028366
540 112508490699800888
541 113031530890758558
542 115396729464931688
543 116042237904593364
544 118417885402425210
545 119014486959411472
546 121547508889289728
547 122104041348957122
548 124648973085802390
549 125320982340155834
550 127862414835578310
551 128493141265309700
552 131219107603644576
553 131793866849404544
554 134513801877722768
555 135230212153013224
556 137958459630652514
557 138613369312202550
558 141526091355119312
559 142135125097254828
560 145059868007014888
561 145799938472272416
562 148714290537731886
563 149409261081547226
564 152537652356813248
565 153166379803063716
566 156283638236663306
567 157072197227034188
568 160200309578152068
569 160917997218308884
570 164258018071873248
571 164919310974128854
572 168266253954904196
573 169082882241264640
574 172417867257840456
575 173180594395557644
576 176758786760817435
577 177439149044672736
578 181006163990659387
579 181872582942481444
580 185449774445582388
581 186231099800045888
582 190045644919055324
583 190764983601173772
584 194587496588680822
585 195485256179669512
586 199288301943573528
587 200117681518270894
588 204204420898732590
589 204939568733646848
590 209010514843835028
591 209956659693663828
592 214031132610388232
593 214882776806532120
594 219231147564959808
595 220010597960239152
596 224361644057627840
597 225339645354870720
598 229671332226981624
599 230571970261146020
600 235227366987248522
601 236015245861254020
602 240643680234249952
603 241678804691414146
604 246310749589148364
605 247236141839630846
606 252176956166928540
607 253011109724101840
608 257958627785298006
609 259023319274906432
610 263944671315438900
611 264915416611860560
612 270198775798048734
613 271045421502000666
614 276297587315305094
615 277426956781770600
616 282677040505101792
617 283670975520268028
618 289278631884291296
619 290170526069315294
620 295782299524835872
621 296933078372668928
622 302504045796735900
623 303553753874682072
624 309539211489503100
625 310444831896956900
626 316387143204603902
627 317607023057722784
628 323550668680784468
629 324618504860396388
630 330968797800066408
631 331913004549319956
632 338255252391195400
633 339502720484287312
634 345798655032121716
635 346928828758600576
636 353690292114906012
637 354646203088224558
638 361362654626635908
639 362679815762497068
640 369394461402152568
641 370531351558068928
642 377695861079921280
643 378700226105555410
644 385857009920211712
645 387204904792619584
646 394299405353969964
647 395502031530579852
648 403133294338866509
649 404139829437243024
650 411715822022912792
651 413128100234620416
652 420685909232290654
653 421901454758637638
654 429973081604576444
655 431035869986163156
656 439088313412047782
657 440529469626307848
658 448518413450681088
659 449797105228891882
660 458391399014478048
661 459440176750182562
662 467955354173819426
663 469474486276048680
664 477971010122146422
665 479265710201445056
666 488333731617341660
667 489440148623696328
668 498494111892337652
669 500034665022910976
670 509011591490516316
671 510359751641884748
672 520006743912761952
673 521103756050393264
674 530661732229275530
675 532291275809370316
676 541815810773884329
677 543174576903302266
678 553356335053186332
679 554507853266082968
680 564667705112167296
681 566300665456338640
682 576353771619957888
683 577781563427680062
684 588594410355769174
685 589736914635682284
686 600437532977183560
687 602163528666667348
688 612835719219483826
689 614261525854983552
690 625671284755529088
691 626852100649667738
692 638215660602616348
693 639956671997147456
694 651200593636673322
695 652706511063127948
696 664795717213155900
697 665960087501950248
698 677932497708002180
699 679762995103535460
700 691699022608124108
701 693178174043090190
702 705922316958202232
703 707141018290727556
704 719836126618267426
705 721683317877802368
706 734228776897702770
707 735792197010066200
708 749300692561550528
709 750485663301430442
710 763857759303241128
711 765780995934276632
712 779085203929566750
713 780630405576491776
714 794849746508167104
715 796098186675299928
716 810244238842848678
717 812178293525126144
718 826170349139438868
719 827791545751755864
720 842862364145534204
721 844046035519756992
722 858932188173983595
723 860964747810435620
724 875779467337068112
725 877385310423789766
726 893209629403195342
727 894457335236621156
728 910217519729873768
729 912242029695555258
730 927820735952102904
731 929480737084897404
732 946239117023584188
733 947428787205971902
734 963986415828537176
735 966128177026228884
736 982584034280396172
737 984217745791202384
738 1001824510213434138
739 1003066722761538018
740 1020592547211519100
741 1022691748362931136
742 1039983284263910760
743 1041694689778923740
744 1060312996007638144
745 1061495658193307880
746 1079867042962816064
747 1082085536207854234
748 1100363063989553028
749 1102026416883955200
750 1121583036068297400
751 1122789423459459400
752 1142220332661052600
753 1144411259340585936
754 1163584487191973532
755 1165340860080284680
756 1185977683048318272
757 1187107121798556210
758 1207488307490959034
759 1209789308893842240
760 1230058330040294700
761 1231718179273156532
762 1253377310690980352
763 1254558874757844568
764 1276081185771287008
765 1278359447593450716
766 1299570612653270976
767 1301326604087525596
768 1324195407911421710
769 1325266233054865024
770 1347844154202328320
771 1350199475454119972
772 1372606015606639346
773 1374279953033686794
774 1398246834394739186
775 1399381829726736336
776 1423170883007490946
777 1425492535625142976
778 1448957587918823112
779 1450711180557225748
780 1476016168595043544
781 1476984757389795072
782 1501916426494324632
783 1504352852304481000
784 1529107325081407461
785 1530776935836722080
786 1557237492968178912
787 1558267024811850154
788 1584558647870544984
789 1586924667793719232
790 1612848937957032144
791 1614561773154376984
792 1642479356438650626
793 1643353795124988408
794 1670867499767783132
795 1673372964445890408
796 1700655193676807620
797 1702264349131265822
798 1731481264061778112
799 1732392162236915280
800 1761410052605033517
801 1763782348284633216
802 1792334533606778922
803 1794021292447415324
804 1824801677130784352
805 1825559544428802816
806 1855853943966516256
807 1858369339632628692
808 1888445807504380968
809 1889985208276582812
810 1922196628235765904
811 1922935571972102142
812 1954868405487975272
813 1957271659472383488
814 1988700354337549092
815 1990341388288783156
816 2024205728560100700
817 2024758123957882192
818 2058124394572635758
819 2060654709268308888
820 2093762037184314168
821 2095177655394795154
822 2130589350921470268
823 2131167577658485684
824 2166284453130738772
825 2168705144674858192
826 2203227548290398432
827 2204739692162329686
828 2242000879159268396
829 2242334855642110926
830 2279033453581449516
831 2281520918692290260
832 2317865832366972748
833 2319179119336976544
834 2358084608977104896
835 2358466116746888568
836 2397004009038035264
837 2399360944389663232
838 2437286736001084926
839 2438666878179666988
840 2479617109602768768
841 2479651939103787434
842 2519899005307410008
843 2522378819376205924
844 2562252478693202870
845 2563428936756874290
846 2606091509088019704
847 2606172608303419404
848 2648475552594850704
849 2650764344688809680
850 2692381108895723106
851 2693553925763634568
852 2738422746294347616
853 2738179862112156098
854 2782301031604213480
855 2784746981385065668
856 2828403420394696146
857 2829335882179489540
858 2876127094512250656
859 2875880928455871622
860 2922264439152556036
861 2924420880335906560
862 2969951487217547256
863 2970943029918401616
864 3020089583484971004
865 3019514122230746064
866 3067776658334840186
867 3070089045075952182
868 3117908738208470528
869 3118582312374906752
870 3169840110048787032
871 3169172260490173588
872 3219885256911211900
873 3221937304647897164
874 3271738041163782048
875 3272511726604742960
876 3326228446159650556
877 3325185725791394326
878 3378003583470495452
879 3380176780278368084
880 3432490065105875556
881 3432812736334853256
882 3488813412289957551
883 3487736601433460922
884 3543159137067473448
885 3545077569626191296
886 3599436761205380058
887 3599847413736411284
888 3658594659562837468
889 3657055978195293184
890 3714788565295128072
891 3716732711071810606
892 3773799096687064368
893 3773800751772275456
894 3834949600860343260
895 3833412547932509796
896 3893871340174974692
897 3895510658265268672
898 3954875817564877410
899 3954909919966948832
900 4019079029094040419
901 4016911762111849236
902 4079850785332279524
903 4081615289582975936
904 4143849885685884522
905 4143471608148415816
906 4210119402501548960
907 4207942176982482830
908 4273913568880265086
909 4275279987562143430
910 4340046014439244368
911 4339576940195973112
912 4409480293606709792
913 4406707441957411920
914 4475297025531750374
915 4476828998775292072
916 4544573285604645608
917 4543647499082574784
918 4616319822701571576
919 4613466099098048004
920 4685385740747598072
921 4686349775579571792
922 4756800548935239420
923 4755877591418638104
924 4832008375082864192
925 4828546767041536154
926 4903152503419708232
927 4904282946872208796
928 4978068131367309204
929 4976554355205787696
930 5055722497789519872
931 5052043119813176682
932 5130222275217816582
933 5130843815560379072
934 5207468219842149846
935 5206017364345994904
936 5288768707038120304
937 5284402509935909724
938 5365607379159309664
939 5366318366944049252
940 5446598093303995824
941 5444351016658098038
942 5530359313087812860
943 5525869231827972552
944 5610853930770287162
945 5611075665599538304
946 5694249229514466720
947 5692048697538454042
948 5782047985037857344
949 5776732373566159460
950 5865017213935855106
951 5865174086934502996
952 5952291177594356424
953 5949343687807263828
954 6042765526298365860
955 6037371690170042688
956 6129570457502211224
957 6129158824243664256
958 6219522712996223664
959 6216551437784808536
960 6314336574627244124
961 6307866127061845008
962 6403597196191981156
963 6403263727193224110
964 6497765484748183338
965 6494048178738044500
966 6595343836042703232
967 6588765828237500908
968 6688866443241977927
969 6687806968364367648
970 6785880281113794672
971 6781930943720573934
972 6887907012527774282
973 6880328327940678912
974 6984111959490507860
975 6983210996827692732
976 7085552598447806116
977 7080773460864256856
978 7190664279853807712
979 7182863590815467676
980 7291441767491596176
981 7289545162700061954
982 7395693580618358514
983 7390832821546714852
984 7505665829681400444
985 7496834549976684792
986 7609163224578629976
987 7607428594068806912
988 7718331280052609356
989 7712457702829720192
990 7831574134962094980
991 7822297611647608848
992 7939747802261356368
993 7937103216567258704
994 8051999008392755712
995 8046108378939754840
996 8170313088839419168
997 8159900481907592282
998 8281562496875666150
999 8278960241506624104
1000 8399057607872850984