0 0
1 1
2 27
3 165
4 712
5 2535
6 8151
7 23527
8 60600
9 140517
10 297595
11 584001
12 1075152
13 1875835
14 3127047
15 5013555
16 7772176
17 11700777
18 17167995
19 24623677
20 34610040
21 47773551
22 64877527
23 86815455
24 114625032
25 149502925
26 192820251
27 246138777
28 311227840
29 390081987
30 484939335
31 598300651
32 732949152
33 891971025
34 1078776667
35 1297122645
36 1551134376
37 1845329527
38 2184642135
39 2574447447
40 3020587480
41 3529397301
42 4107732027
43 4762994545
44 5503163952
45 6336824715
46 7273196551
47 8322165027
48 9494312880
49 10800952057
50 12254156475
51 13866795501
52 15652568152
53 17626038015
54 19802668887
55 22198861135
56 24831988776
57 27720437277
58 30883642075
59 34342127817
60 38117548320
61 42232727251
62 46711699527
63 51579753435
64 56863473472
65 62590783905
66 68790993051
67 75494838277
68 82734531720
69 90543806727
70 98957965015
71 108013924551
72 117750268152
73 128207292805
74 139427059707
75 151453445025
76 164332191376
77 178110960027
78 192839383815
79 208569120787
80 225353908560
81 243249619401
82 262314316027
83 282608308125
84 304194209592
85 327136996495
86 351504065751
87 377365294527
88 404793100360
89 433862501997
90 464651180955
91 497239543801
92 531710785152
93 568150951395
94 606649005127
95 647296890315
96 690189598176
97 735425233777
98 783105083355
99 833333682357
100 886218884200
101 941871929751
102 1000407517527
103 1061943874615
104 1126602828312
105 1194509878485
106 1265794270651
107 1340589069777
108 1419031234800
109 1501261693867
110 1587425420295
111 1677671509251
112 1772153255152
113 1871028229785
114 1974458361147
115 2082610013005
116 2195654065176
117 2313765994527
118 2437125956695
119 2565918868527
120 2700334491240
121 2840567514301
122 2986817640027
123 3139289668905
124 3298193585632
125 3463744645875
126 3636163463751
127 3815676100027
128 4002514151040
129 4196914838337
130 4399121099035
131 4609381676901
132 4827951214152
133 5055090343975
134 5291065783767
135 5536150429095
136 5790623448376
137 6054770378277
138 6328883219835
139 6613260535297
140 6908207545680
141 7214036229051
142 7531065419527
143 7859620906995
144 8200035537552
145 8552649314665
146 8917809501051
147 9295870721277
148 9687195065080
149 10092152191407
150 10511119433175
151 10944481902751
152 11392632598152
153 11855972509965
154 12334910728987
155 12829864554585
156 13341259603776
157 13869529921027
158 14415118088775
159 14978475338667
160 15560061663520
161 16160345930001
162 16779805992027
163 17418928804885
164 18078210540072
165 18758156700855
166 19459282238551
167 20182111669527
168 20927179192920
169 21695028809077
170 22486214438715
171 23301300042801
172 24140859743152
173 25005477943755
174 25895749452807
175 26812279605475
176 27755684387376
177 28726590558777
178 29725635779515
179 30753468734637
180 31810749260760
181 32898148473151
182 34016348893527
183 35166044578575
184 36347941249192
185 37562756420445
186 38811219532251
187 40094072080777
188 41412067750560
189 42765972547347
190 44156564931655
191 45584635953051
192 47050989385152
193 48556441861345
194 50101823011227
195 51687975597765
196 53315755655176
197 54986032627527
198 56699689508055
199 58457622979207
200 60260743553400
201 62109975714501
202 64006258060027
203 65950543444065
204 67943799120912
205 69987006889435
206 72081163238151
207 74227279491027
208 76426381954000
209 78679512062217
210 80987726527995
211 83352097489501
212 85773712660152
213 88253675478735
214 90793105260247
215 93393137347455
216 96054923263176
217 98779630863277
218 101568444490395
219 104422565128377
220 107343210557440
221 110331615510051
222 113389031827527
223 116516728617355
224 119715992411232
225 122988127323825
226 126334455212251
227 129756315836277
228 133255067019240
229 136832084809687
230 140488763643735
231 144226516508151
232 148046775104152
233 151950990011925
234 155940630855867
235 160017186470545
236 164182165067376
237 168437094402027
238 172783521942535
239 177223015038147
240 181757161088880
241 186387567715801
242 191115862932027
243 195943695314445
244 200872734176152
245 205904669739615
246 211041213310551
247 216284097452527
248 221635076162280
249 227095925045757
250 232668441494875
251 238354444865001
252 244155776653152
253 250074300676915
254 256111903254087
255 262270493383035
256 268552002923776
257 274958386779777
258 281491623080475
259 288153713364517
260 294946682763720
261 301872580187751
262 308933478509527
263 316131474751335
264 323468690271672
265 330947270952805
266 338569387389051
267 346337235075777
268 354253034599120
269 362319031826427
270 370537498097415
271 378910730416051
272 387441051643152
273 396130810689705
274 404982382710907
275 413998169300925
276 423180598688376
277 432532125932527
278 442055233120215
279 451752429563487
280 461626251997960
281 471679264781901
282 481914060096027
283 492333258144025
284 502939507353792
285 513735484579395
286 524723895303751
287 535907473842027
288 547288983545760
289 558871217007697
290 570656996267355
291 582649173017301
292 594850628810152
293 607264275266295
294 619893054282327
295 632739938240215
296 645807930217176
297 659100064196277
298 672619405277755
299 686369049891057
300 700352126007600
301 714571793354251
302 729031243627527
303 743733700708515
304 758682420878512
305 773880693035385
306 789331838910651
307 805039213287277
308 821006204218200
309 837236233245567
310 853732755620695
311 870499260524751
312 887539271290152
313 904856345622685
314 922454075824347
315 940336089016905
316 958506047366176
317 976967648307027
318 995724624769095
319 1014780745403227
320 1034139814808640
321 1053805673760801
322 1073782199440027
323 1094073305660805
324 1114682943101832
325 1135615099536775
326 1156873800065751
327 1178463107347527
328 1200387121832440
329 1222649981996037
330 1245255864573435
331 1268208984794401
332 1291513596619152
333 1315173992974875
334 1339194505992967
335 1363579507246995
336 1388333407991376
337 1413460659400777
338 1438965752810235
339 1464853219955997
340 1491127633217080
341 1517793605857551
342 1544855792269527
343 1572318888216895
344 1600187631079752
345 1628466800099565
346 1657161216625051
347 1686275744358777
348 1715815289604480
349 1745784801515107
350 1776189272341575
351 1807033737682251
352 1838323276733152
353 1870063012538865
354 1902258112244187
355 1934913787346485
356 1968035293948776
357 2001627933013527
358 2035697050617175
359 2070248038205367
360 2105286332848920
361 2140817417500501
362 2176846821252027
363 2213380119592785
364 2250422934668272
365 2287980935539755
366 2326059838444551
367 2364665407057027
368 2403803452750320
369 2443479834858777
370 2483700460941115
371 2524471287044301
372 2565798317968152
373 2607687607530655
374 2650145258834007
375 2693177424531375
376 2736790307094376
377 2780990159081277
378 2825783283405915
379 2871176033607337
380 2917174814120160
381 2963786080545651
382 3011016339923527
383 3058872151004475
384 3107360124523392
385 3156486923473345
386 3206259263380251
387 3256683912578277
388 3307767692485960
389 3359517477883047
390 3411940197188055
391 3465042832736551
392 3518832421060152
393 3573316053166245
394 3628500874818427
395 3684394086817665
396 3741002945284176
397 3798334761940027
398 3856396904392455
399 3915196796417907
400 3974741918246800
401 4035039806849001
402 4096098056220027
403 4157924317667965
404 4220526300101112
405 4283911770316335
406 4348088553288151
407 4413064532458527
408 4478847650027400
409 4545445907243917
410 4612867364698395
411 4681120142615001
412 4750212421145152
413 4820152440661635
414 4890948502053447
415 4962608967021355
416 5035142258374176
417 5108556860325777
418 5182861318792795
419 5258064241693077
420 5334174299244840
421 5411200224266551
422 5489150812477527
423 5568034922799255
424 5647861477657432
425 5728639463284725
426 5810377930024251
427 5893085992633777
428 5976772830590640
429 6061447688397387
430 6147119875888135
431 6233798768535651
432 6321493807759152
433 6410214501232825
434 6499970423195067
435 6590771214758445
436 6682626584220376
437 6775546307374527
438 6869540227822935
439 6964618257288847
440 7060790375930280
441 7158066632654301
442 7256457145432027
443 7355972101614345
444 7456621758248352
445 7558416442394515
446 7661366551444551
447 7765482553440027
448 7870774987391680
449 7977254463599457
450 8084931663973275
451 8193817342354501
452 8303922324838152
453 8415257510095815
454 8527833869699287
455 8641662448444935
456 8756754364678776
457 8873120810622277
458 8990773052698875
459 9109722431861217
460 9229980363919120
461 9351558339868251
462 9474467926219527
463 9598720765329235
464 9724328575729872
465 9851303152461705
466 9979656367405051
467 10109400169613277
468 10240546585646520
469 10373107719906127
470 10507095754969815
471 10642522951927551
472 10779401650718152
473 10917744270466605
474 11057563309822107
475 11198871347296825
476 11341681041605376
477 11486005132005027
478 11631856438636615
479 11779247862866187
480 11928192387627360
481 12078703077764401
482 12230793080376027
483 12384475625159925
484 12539764024757992
485 12696671675102295
486 12855212055761751
487 13015398730289527
488 13177245346571160
489 13340765637173397
490 13505973419693755
491 13672882597110801
492 13841507158135152
493 14011861177561195
494 14183958816619527
495 14357814323330115
496 14533442032856176
497 14710856367858777
498 14890071838852155
499 15071103044559757
500 15253964672271000
501 15438671498198751
502 15625238387837527
503 15813680296322415
504 16004012268788712
505 16196249440732285
506 16390407038370651
507 16586500379004777
508 16784544871381600
509 16984556016057267
510 17186549405761095
511 17390540725760251
512 17596545754225152
513 17804580362595585
514 18014660515947547
515 18226802273360805
516 18441021788287176
517 18657335308919527
518 18875759178561495
519 19096309835997927
520 19319003815866040
521 19543857749027301
522 19770888362940027
523 20000112482032705
524 20231547028078032
525 20465209020567675
526 20701115577087751
527 20939283913695027
528 21179731345293840
529 21422475286013737
530 21667533249587835
531 21914922849731901
532 22164661800524152
533 22416767916785775
534 22671259114462167
535 22928153411004895
536 23187468925754376
537 23449223880323277
538 23713436598980635
539 23980125509036697
540 24249309141228480
541 24521006130106051
542 24795235214419527
543 25072015237506795
544 25351365147681952
545 25633303998624465
546 25917850949769051
547 26205025266696277
548 26494846321523880
549 26787333593298807
550 27082506668389975
551 27380385240881751
552 27680989112968152
553 27984338195347765
554 28290452507619387
555 28599352178678385
556 28911057447113776
557 29225588661606027
558 29542966281325575
559 29863210876332067
560 30186343127974320
561 30512383829291001
562 30841353885412027
563 31173274313960685
564 31508166245456472
565 31846050923718655
566 32186949706270551
567 32530884064744527
568 32877875585287720
569 33227945968968477
570 33581117032183515
571 33937410707065801
572 34296849041893152
573 34659454201497555
574 35025248467675207
575 35394254239597275
576 35766494034221376
577 36141990486703777
578 36520766350812315
579 36902844499340037
580 37288247924519560
581 37676999738438151
582 38069123173453527
583 38464641582610375
584 38863578440057592
585 39265957341466245
586 39671802004448251
587 40081136268975777
588 40493984097801360
589 40910369576878747
590 41330316915784455
591 41753850448140051
592 42180994632035152
593 42611774050451145
594 43046213411685627
595 43484337549777565
596 43926171424933176
597 44371740123952527
598 44821068860656855
599 45274182976316607
600 45731107940080200
601 46191869349403501
602 46656492930480027
603 47125004538671865
604 47597430158941312
605 48073795906283235
606 48554128026158151
607 49038452894926027
608 49526797020280800
609 50019187041685617
610 50515649730808795
611 51016211991960501
612 51520900862530152
613 52029743513424535
614 52542767249506647
615 53059999510035255
616 53581467869105176
617 54107200036088277
618 54637223856075195
619 55171567310317777
620 55710258516672240
621 56253325730043051
622 56800797342827527
623 57352701885361155
624 57909068026363632
625 58469924573385625
626 59035300473256251
627 59605224812531277
628 60179726817942040
629 60758835856845087
630 61342581437672535
631 61930993210383151
632 62524100966914152
633 63121934641633725
634 63724524311794267
635 64331900197986345
636 64944092664593376
637 65561132220247027
638 66183049518283335
639 66809875357199547
640 67441640681111680
641 68078376580212801
642 68720114291232027
643 69366885197894245
644 70018720831380552
645 70675652870789415
646 71337713143598551
647 72004933626127527
648 72677346444001080
649 73354983872613157
650 74037878337591675
651 74726062415264001
652 75419568833123152
653 76118430470294715
654 76822680358004487
655 77532351680046835
656 78247477773253776
657 78968092127964777
658 79694228388497275
659 80425920353617917
660 81163201977014520
661 81906107367768751
662 82654670790829527
663 83408926667487135
664 84168909575848072
665 84934654251310605
666 85706195587041051
667 86483568634450777
668 87266808603673920
669 88055950864045827
670 88851030944582215
671 89652084534459051
672 90459147483493152
673 91272255802623505
674 92091445664393307
675 92916753403432725
676 93748215516942376
677 94585868665177527
678 95429749671933015
679 96279895525028887
680 97136343376796760
681 97999130544566901
682 98868294511156027
683 99743872925355825
684 100625903602422192
685 101514424524565195
686 102409473841439751
687 103311089870637027
688 104219311098176560
689 105134176178999097
690 106055723937460155
691 106983993367824301
692 107919023634760152
693 108860854073836095
694 109809524192016727
695 110765073668160015
696 111727542353515176
697 112696970272221277
698 113673397621806555
699 114656864773688457
700 115647412273674400
701 116645080842463251
702 117649911376147527
703 118661944946716315
704 119681222802558912
705 120707786368969185
706 121741677248650651
707 122782937222222277
708 123831608248725000
709 124887732466128967
710 125951352191841495
711 127022509923215751
712 128101248338060152
713 129187610295148485
714 130281638834730747
715 131383377179044705
716 132492868732828176
717 133610157083832027
718 134735286003333895
719 135868299446652627
720 137009241553663440
721 138158156649313801
722 139315089244140027
723 140480084034784605
724 141653185904514232
725 142834439923738575
726 144023891350529751
727 145221585631142527
728 146427568400535240
729 147641885482891437
730 148864582892142235
731 150095706832489401
732 151335303698929152
733 152583420077776675
734 153840102747191367
735 155105398677702795
736 156379355032737376
737 157662019169145777
738 158953438637731035
739 160253661183777397
740 161562734747579880
741 162880707464974551
742 164207627667869527
743 165543543884776695
744 166888504841344152
745 168242559460889365
746 169605756864933051
747 170978146373733777
748 172359777506823280
749 173750699983542507
750 175150963723578375
751 176560618847501251
752 177979715677303152
753 179408304736936665
754 180846436752854587
755 182294162654550285
756 183751533575098776
757 185218600851698527
758 186695416026213975
759 188182030845718767
760 189678497263039720
761 191184867437301501
762 192701193734472027
763 194227528727908585
764 195763925198904672
765 197310436137237555
766 198867114741716551
767 200434014420732027
768 202011188792805120
769 203598691687138177
770 205196577144165915
771 206804899416107301
772 208423712967518152
773 210053072475844455
774 211693032831976407
775 213343649140803175
776 215004976721768376
777 216677071109426277
778 218359988053998715
779 220053783521932737
780 221758513696458960
781 223474234978150651
782 225201003985483527
783 226938877555396275
784 228687912743851792
785 230448166826399145
786 232219697298736251
787 234002561877273277
788 235796818499696760
789 237602525325534447
790 239419740736720855
791 241248523338163551
792 243088931958310152
793 244941025649716045
794 246804863689612827
795 248680505580477465
796 250568011050602176
797 252467440054665027
798 254378852774301255
799 256302309618675307
800 258237871225053600
801 260185598459378001
802 262145552416840027
803 264117794422455765
804 266102386031641512
805 268099389030790135
806 270108865437848151
807 272130877502893527
808 274165487708714200
809 276212758771387317
810 278272753640859195
811 280345535501526001
812 282431167772815152
813 284529714109767435
814 286641238403619847
815 288765804782389155
816 290903477611456176
817 293054321494150777
818 295218401272337595
819 297395782027002477
820 299586529078839640
821 301790707988839551
822 304008384558877527
823 306239624832303055
824 308484495094529832
825 310743061873626525
826 313015391940908251
827 315301552311528777
828 317601610245073440
829 319915633246152787
830 322243689064996935
831 324585845698050651
832 326942171388569152
833 329312734627214625
834 331697604152653467
835 334096848952154245
836 336510538262186376
837 338938741569019527
838 341381528609323735
839 343838969370770247
840 346311134092633080
841 348798093266391301
842 351299917636332027
843 353816678200154145
844 356348446209572752
845 358895293170924315
846 361457290845772551
847 364034511251515027
848 366627026661990480
849 369234909608086857
850 371858232878350075
851 374497069519593501
852 377151492837508152
853 379821576397273615
854 382507394024169687
855 385209019804188735
856 387926528084648776
857 390659993474807277
858 393409490846475675
859 396175095334634617
860 398956882338049920
861 401754927519889251
862 404569306808339527
863 407400096397225035
864 410247372746626272
865 413111212583499505
866 415991692902297051
867 418888890965588277
868 421802884304681320
869 424733750720245527
870 427681568282934615
871 430646415334010551
872 433628370485968152
873 436627512623160405
874 439643920902424507
875 442677674753708625
876 445728853880699376
877 448797538261450027
878 451883808149009415
879 454987744072051587
880 458109426835506160
881 461248937521189401
882 464406357488436027
883 467581768374731725
884 470775252096346392
885 473986890848968095
886 477216767108337751
887 480464963630884527
888 483731563454361960
889 487016649898484797
890 490320306565566555
891 493642617341157801
892 496983666394685152
893 500343538180090995
894 503722317436473927
895 507120089188729915
896 510536938748194176
897 513972951713283777
898 517428213970140955
899 520902811693277157
900 524396831346217800
901 527910359682147751
902 531443483744557527
903 534996290867890215
904 538568868678189112
905 542161305093746085
906 545773688325750651
907 549406106878939777
908 553058649552248400
909 556731405439460667
910 560424463929861895
911 564137914708891251
912 567871847758795152
913 571626353359281385
914 575401522088173947
915 579197444822068605
916 583014212736989176
917 586851917309044527
918 590710650315086295
919 594590503833367327
920 598491570244200840
921 602413942230620301
922 606357712779040027
923 610322975179916505
924 614309823028410432
925 618318350225049475
926 622348650976391751
927 626400819795690027
928 630474951503556640
929 634571141228629137
930 638689484408236635
931 642830076789066901
932 646993014427834152
933 651178393691947575
934 655386311260180567
935 659616864123340695
936 663870149584940376
937 668146265261868277
938 672445309085061435
939 676767379300178097
940 681112574468271280
941 685480993466463051
942 689872735488619527
943 694287900046026595
944 698726586968066352
945 703188896402894265
946 707674928818117051
947 712184785001471277
948 716718566061502680
949 721276373428246207
950 725858308853906775
951 730464474413540751
952 735094972505738152
953 739749905853305565
954 744429377503949787
955 749133490830962185
956 753862349533903776
957 758616057639291027
958 763394719501282375
959 768198439802365467
960 773027323554045120
961 777881476097532001
962 782761003104432027
963 787666010577436485
964 792596604851012872
965 797552892592096455
966 802534980800782551
967 807542976811019527
968 812576988291302520
969 817637123245367877
970 822723490012888315
971 827836197270168801
972 832975354030843152
973 838141069646571355
974 843333453807737607
975 848552616544149075
976 853798668225735376
977 859071719563248777
978 864371881608965115
979 869699265757385437
980 875053983745938360
981 880436147655683151
982 885845869912013527
983 891283263285362175
984 896748440891905992
985 902241516194272045
986 907762603002244251
987 913311815473470777
988 918889268114172160
989 924495075779850147
990 930129353675997255
991 935792217358807051
992 941483782735885152
993 947204166066960945
994 952953483964600027
995 958731853394917365
996 964539391678291176
997 970376216490077527
998 976242445861325655
999 982138198179494007
1000 988063592189167000