0 1
1 1
2 3
3 7
4 17
5 35
6 76
7 149
8 291
9 539
10 974
11 1691
12 2874
13 4730
14 7620
15 11986
16 18485
17 27944
18 41550
19 60744
20 87527
21 124338
22 174403
23 241650
24 331153
25 448987
26 602853
27 801943
28 1057615
29 1383343
30 1795578
31 2313595
32 2960656
33 3763879
34 4755505
35 5972927
36 7460196
37 9267980
38 11455495
39 14090516
40 17251491
41 21027776
42 25522148
43 30850944
44 37147156
45 44560718
46 53261850
47 63441708
48 75316234
49 89126745
50 105144614
51 123672039
52 145047117
53 169645101
54 197884174
55 230226709
56 267186065
57 309328195
58 357278963
59 411726403
60 473428975
61 543217862
62 622006606
63 710793842
64 810673619
65 922839054
66 1048593818
67 1189355960
68 1346671058
69 1522216670
70 1717816448
71 1935445694
72 2177246983
73 2445535989
74 2742819185
75 3071800535
76 3435400339
77 3836763411
78 4279279761
79 4766593183
80 5302624491
81 5891581183
82 6537982213
83 7246669423
84 8022834536
85 8872031266
86 9800205329
87 10813707976
88 11919327820
89 13124306560
90 14436373567
91 15863762432
92 17415249192
93 19100170616
94 20928464676
95 22910691516
96 25058077104
97 27382535409
98 29896716299
99 32614029831
100 35548696890
101 38715776625
102 42131220960
103 45811903485
104 49775678895
105 54041414537
106 58629053055
107 63559647723
108 68855429522
109 74539844338
110 80637625843
111 87174835750
112 94178940545
113 101678856136
114 109705029766
115 118289487008
116 127465920222
117 137269739306
118 147738164615
119 158910282794
120 170827145714
121 183531829085
122 197069539005
123 211487674871
124 226835941079
125 243166415913
126 260533670067
127 278994838947
128 298609749724
129 319440998679
130 341554084312
131 365017491399
132 389902831948
133 416284933252
134 444241988523
135 473855650824
136 505211190490
137 538397596864
138 573507744556
139 610638499840
140 649890897845
141 691370255620
142 735186357214
143 781453575460
144 830291066982
145 881822899535
146 936178259167
147 993491585255
148 1053902786469
149 1117557385685
150 1184606747221
151 1255208228001
152 1329525418429
153 1407728302227
154 1489993507275
155 1576504476595
156 1667451731614
157 1763033050494
158 1863453746482
159 1968926855994
160 2079673428204
161 2195922725496
162 2317912527058
163 2445889337560
164 2580108707402
165 2720835452496
166 2868343986977
167 3022918556854
168 3184853588099
169 3354453929669
170 3532035220112
171 3717924142823
172 3912458806619
173 4115989016315
174 4328876670341
175 4551496041947
176 4784234196986
177 5027491288943
178 5281680992141
179 5547230813663
180 5824582545393
181 6114192587760
182 6416532424085
183 6732088959504
184 7061365012312
185 7404879671662
186 7763168809488
187 8136785451520
188 8526300313424
189 8932302188656
190 9355398503491
191 9796215725296
192 10255399940204
193 10733617276129
194 11231554506899
195 11749919493903
196 12289441810753
197 12850873207513
198 13434988260020
199 14042584850405
200 14674484845264
201 15331534596539
202 16014605642391
203 16724595232571
204 17462427056106
205 18229051784844
206 19025447832332
207 19852621919790
208 20711609859597
209 21603477148008
210 22529319777965
211 23490264851592
212 24487471426902
213 25522131154722
214 26595469152267
215 27708744669214
216 28863251992841
217 30060321136045
218 31301318779029
219 32587648983895
220 33920754165608
221 35302115838079
222 36733255619527
223 38215736002379
224 39751161397992
225 41341178935645
226 42987479538881
227 44691798758711
228 46455917886900
229 48281664815228
230 50170915191346
231 52125593309348
232 54147673299974
233 56239180058048
234 58402190472564
235 60638834382576
236 62951295852772
237 65341814163516
238 67812685123426
239 70366262099100
240 73004957370687
241 75731243192377
242 78547653197031
243 81456783493351
244 84461294110333
245 87563910137351
246 90767423214646
247 94074692706889
248 97488647245993
249 101012285944291
250 104648679980410
251 108400973858275
252 112272387042486
253 116266215253430
254 120385832158678
255 124634690710822
256 129016324884843
257 133534351065368
258 138192469836938
259 142994467410168
260 147944217471923
261 153045682657230
262 158302916449029
263 163720064702766
264 169301367602623
265 175051161228243
266 180973879574689
267 187074056168391
268 193356326139939
269 199825427896419
270 206486205254724
271 213343609158895
272 220402699881446
273 227668648793311
274 235146740621717
275 242842375280423
276 250761070191800
277 258908462165672
278 267290309793625
279 275912495384024
280 284781027416777
281 293902042542464
282 303281808105752
283 312926724196352
284 322843326249080
285 333038287155034
286 343518419925932
287 354290679873704
288 365362167347560
289 376740129969105
290 388431965450970
291 400445223895815
292 412787610683545
293 425466988842945
294 438491382016200
295 451868976889945
296 465608126245895
297 479717351460235
298 494205345627055
299 509080976134795
300 524353287871771
301 540031505865826
302 556125038581328
303 572643480631222
304 589596616151257
305 606994421594030
306 624847069190006
307 643164929809064
308 661958576517966
309 681238787518874
310 701016549788994
311 721303062105626
312 742109738777829
313 763448212743165
314 785330339401325
315 807768199792631
316 830774104518375
317 854360597011239
318 878540457552795
319 903326706620019
320 928732609010497
321 954771677275383
322 981457675936713
323 1008804625017255
324 1036826804360348
325 1065538757240782
326 1094955294798003
327 1125091499738668
328 1155962730866930
329 1187584626889408
330 1219973111053923
331 1253144395040000
332 1287114983717196
333 1321901679132404
334 1357521585370790
335 1393992112651272
336 1431330982301406
337 1469556230943785
338 1508686215596655
339 1548739617962471
340 1589735449636886
341 1631693056511141
342 1674632124101418
343 1718572682047089
344 1763535109572181
345 1809540140091713
346 1856608866787195
347 1904762747333043
348 1954023609598414
349 2004413656474990
350 2055955471717909
351 2108672024887114
352 2162586677308567
353 2217723187141816
354 2274105715474114
355 2331758831495104
356 2390707518736570
357 2450977180367110
358 2512593645558313
359 2575583174912038
360 2639972466966320
361 2705788663735397
362 2773059357368761
363 2841812595817127
364 2912076889624299
365 2983881217732749
366 3057255034421933
367 3132228275232855
368 3208831364066578
369 3287095219241295
370 3367051260730668
371 3448731416367039
372 3532168129233568
373 3617394363992544
374 3704443614445405
375 3793349910000380
376 3884147823378864
377 3976872477236736
378 4071559552031776
379 4168245292776448
380 4266966517081161
381 4367760622053088
382 4470665592493328
383 4575720007956448
384 4682963051116196
385 4792434514963511
386 4904174811355939
387 5018224978369031
388 5134626689006705
389 5253422258721065
390 5374654654299487
391 5498367501529397
392 5624605094277587
393 5753412402315611
394 5884835080567751
395 6018919477112811
396 6155712642616474
397 6295262338485594
398 6437617046501204
399 6582825977140926
400 6730939079388610
401 6882007049241000
402 7036081339710510
403 7193214169491400
404 7353458533171910
405 7516868210076732
406 7683497774663635
407 7853402605558738
408 8026638896154497
409 8203263663812173
410 8383334760678588
411 8566910883072535
412 8754051582494575
413 8944817275214671
414 9139269253492271
415 9337469695339103
416 9539481675966912
417 9745369177742951
418 9955197101839185
419 10169031278397719
420 10386938478399509
421 10608986424012780
422 10835243800699415
423 11065780267764276
424 11300666470671774
425 11539974051814558
426 11783775663058692
427 12032144976703872
428 12285156698275764
429 12542886577696044
430 12805411422294357
431 13072809108206604
432 13345158593625338
433 13622539930397977
434 13905034277534583
435 14192723913025119
436 14485692247575725
437 14784023836664269
438 15087804394524766
439 15397120806411545
440 15712061142851590
441 16032714672136835
442 16359171874815059
443 16691524456429955
444 17029865362270182
445 17374288790327480
446 17724890206324062
447 18081766356908690
448 18445015284932099
449 18814736342901080
450 19191030208522841
451 19573998898385976
452 19963745783794354
453 20360375604695742
454 20763994485773965
455 21174709950646090
456 21592630938233719
457 22017867817197109
458 22450532402607057
459 22890737970636679
460 23338599275502124
461 23794232564433331
462 24257755594905313
463 24729287649855295
464 25208949555225982
465 25696863695451141
466 26193154031278117
467 26697946115543599
468 27211367111297544
469 27733545807835544
470 28264612639146932
471 28804699700225768
472 29353940765809404
473 29912471306990720
474 30480428510269736
475 31057951294432992
476 31645180329940936
477 32242258056097368
478 32849328700738356
479 33466538297714328
480 34094034706904013
481 34731967631974065
482 35380488640741675
483 36039751183235079
484 36709910612369097
485 37391124202330507
486 38083551169590448
487 38787352691578525
488 39502691928056159
489 40229734040103211
490 40968646211816486
491 41719597669632811
492 42482759704377074
493 43258305690885074
494 44046411110425624
495 44847253570647898
496 45661012828340273
497 46487870809727048
498 47328011633589350
499 48181621631873000
500 49048889373196959
501 49930005683797514
502 50825163671386391
503 51734558746456586
504 52658388646515421
505 53596853457713739
506 54550155639479837
507 55518500046497655
508 56502093953702647
509 57501147078634743
510 58515871606822910
511 59546482214473027
512 60593196094267532
513 61656232978414807
514 62735815164823897
515 63832167540542159
516 64945517608331756
517 66076095510455140
518 67224134055680699
519 68389868743442620
520 69573537791235103
521 70775382159173824
522 71995645577806412
523 73234574573033984
524 74492418494365212
525 75769429540225990
526 77065862786615406
527 78381976212831236
528 79718030730555990
529 81074290209955593
530 82451021509224366
531 83848494501084903
532 85266982102749189
533 86706760302848373
534 88168108191838674
535 89651307989317821
536 91156645074904557
537 92684408015970771
538 94234888598951211
539 95808381857519955
540 97405186104360007
541 99025602959739742
542 100669937383772226
543 102338497705421146
544 104031595655204783
545 105749546394661646
546 107492668549529266
547 109261284239624024
548 111055719112525098
549 112876302373898486
550 114723366821640980
551 116597248876678550
552 118498288617601011
553 120426829811888645
554 122383219951068393
555 124367810282399767
556 126380955844505723
557 128423015499549083
558 130494351969369813
559 132595331868104103
560 134726325738859943
561 136887708086810415
562 139079857416360109
563 141303156264744351
564 143557991239718128
565 145844753053613338
566 148163836561582629
567 150515640796146736
568 152900569005944584
569 155319028690802944
570 157771431641026119
571 160258193972938240
572 162779736168745456
573 165336483112584016
574 167928864130905112
575 170557313029062068
576 173222268132251100
577 175924172322587297
578 178663473080635315
579 181440622523007239
580 184256077444432722
581 187110299355912569
582 190003754527362692
583 192936914026271877
584 195910253760953515
585 198924254519742329
586 201979402014802167
587 205076186921896059
588 208215104924784970
589 211396656755518410
590 214621348239459815
591 217889690336132430
592 221202199184818365
593 224559396145995240
594 227961807847544350
595 231409966226724640
596 234904408577025590
597 238445677590714370
598 242034321406279835
599 245670893651588290
600 249355953491955166
601 253090065673854701
602 256873800573656053
603 260707734241923287
604 264592448452760447
605 268528530748739025
606 272516574490889111
607 276557178904198379
608 280650949128286616
609 284798496263513159
610 289000437422279264
611 293257395775781111
612 297570000605977684
613 301938887352932700
614 306364697667485855
615 310848079459221776
616 315389686949787190
617 319990180721525184
618 324650227771477140
619 329370501560623744
620 334151682068610717
621 338994455843635228
622 343899516057837298
623 348867562557870460
624 353899301920997618
625 358995447506287327
626 364156719511453703
627 369383845024717543
628 374677558082330845
629 380038599721142173
630 385467718036846393
631 390965668237193705
632 396533212701004761
633 402171121032063779
634 407880170118838275
635 413661144189096867
636 419514834870374166
637 425442041245251990
638 431443569912610790
639 437520235043614626
640 443672858443687656
641 449902269609244056
642 456209305790431338
643 462594812048542584
644 469059641319567906
645 475604654472331208
646 482230720372786965
647 488938715942923278
648 495729526225846319
649 502604044445385685
650 509563172072009704
651 516607818883175239
652 523738903030009667
653 530957351098448131
654 538264098176725129
655 545660087917234499
656 553146272604873750
657 560723613219670175
658 568393079505913013
659 576155650035588623
660 584012312278344665
661 591964062665668232
662 600011906661726441
663 608156858828331512
664 616399942896590804
665 624742191832703694
666 633184647910465848
667 641728362777830400
668 650374397530311448
669 659123822778354120
670 667977718721570263
671 676937175216962184
672 686003291854035928
673 695177178023810449
674 704459952994854075
675 713852745983124975
676 723356696228861689
677 732972953067300961
678 742702676006469016
679 752547034798706413
680 762507209519406956
681 772584390639396043
682 782779779104547343
683 793094586409061323
684 803530034676006306
685 814087356731426756
686 824767796185856224
687 835572607509302486
688 846503056113661065
689 857560418428624520
690 868745981985045157
691 880061045491695912
692 891506918919630382
693 903084923579843706
694 914796392208557151
695 926642669045827606
696 938625109921805269
697 950745082336218429
698 963003965545653709
699 975403150643964471
700 987944040650500080
701 1000628050591487175
702 1013456607589257835
703 1026431150944528915
704 1039553132226678500
705 1052824015356973677
706 1066245276699820265
707 1079818405146988903
708 1093544902209888572
709 1107426282104714708
710 1121464071845797958
711 1135659811331724620
712 1150015053439684130
713 1164531364112613056
714 1179210322454592476
715 1194053520818938448
716 1209062564904700652
717 1224239073845750996
718 1239584680308306230
719 1255101030581065844
720 1270789784673811179
721 1286652616408514025
722 1302691213519064975
723 1318907277743405031
724 1335302524924303669
725 1351878685102566703
726 1368637502618917242
727 1385580736208199697
728 1402710159102417029
729 1420027559125983859
730 1437534738799840402
731 1455233515437807859
732 1473125721251832878
733 1491213203449364302
734 1509497824339782218
735 1527981461432850414
736 1546666007546248135
737 1565553370905152824
738 1584645475250929826
739 1603944259941762200
740 1623451680062553835
741 1643169706526661350
742 1663100326186927929
743 1683245541938572550
744 1703607372831409707
745 1724187854173812675
746 1744989037646175257
747 1766012991406004775
748 1787261800202541579
749 1808737565483037675
750 1830442405508591336
751 1852378455461525751
752 1874547867562495554
753 1896952811179022607
754 1919595472943788605
755 1942478056864385335
756 1965602784442850624
757 1988971894786546624
758 2012587644728997357
759 2036452308941952064
760 2060568180057437669
761 2084937568781065216
762 2109562804015355968
763 2134446232974202880
764 2159590221307528512
765 2184997153216960786
766 2210669431581734432
767 2236609478075639744
768 2262819733294226964
769 2289302656872938369
770 2316060727615676002
771 2343096443614176263
772 2370412322377851089
773 2398010900954465225
774 2425894736061310956
775 2454066404207097537
776 2482528501824519811
777 2511283645393420443
778 2540334471574661671
779 2569683637334620443
780 2599333820080424883
781 2629287717785690170
782 2659548049127181540
783 2690117553611852254
784 2720998991714839957
785 2752195145007869102
786 2783708816298642958
787 2815542829760516680
788 2847700031073347494
789 2880183287554500466
790 2912995488301063606
791 2946139544322248626
792 2979618388683033969
793 3013434976637865869
794 3047592285775792549
795 3082093316155529143
796 3116941090451987343
797 3152138654092767983
798 3187689075406150655
799 3223595445758916795
800 3259860879705864029
801 3296488515129024039
802 3333481513388605041
803 3370843059463668951
804 3408576362104566436
805 3446684653974976134
806 3485171191805897767
807 3524039256539118420
808 3563292153482665422
809 3602933212455764928
810 3642965787945821355
811 3683393259254768512
812 3724219030657641812
813 3765446531550388492
814 3807079216609932602
815 3849120565943511104
816 3891574085250298346
817 3934443305972167385
818 3977731785456941719
819 4021443107110648295
820 4065580880562295598
821 4110148741817685869
822 4155150353425787822
823 4200589404634005689
824 4246469611556214257
825 4292794717329553585
826 4339568492284023731
827 4386794734100873411
828 4434477267983823430
829 4482619946818945158
830 4531226651347582761
831 4580301290327790258
832 4629847800708848179
833 4679870147794329048
834 4730372325418278234
835 4781358356109802816
836 4832832291270986642
837 4884798211343072926
838 4937260225986008221
839 4990222474246288510
840 5043689124738203452
841 5097664375813239157
842 5152152455743094321
843 5207157622890710791
844 5262684165894953683
845 5318736403843341941
846 5375318686458464561
847 5432435394272302559
848 5490090938814453678
849 5548289762788117631
850 5607036340260021300
851 5666335176838139375
852 5726190809863392936
853 5786607808588995960
854 5847590774374000433
855 5909144340864342212
856 5971273174188122028
857 6033981973138424448
858 6097275469370409288
859 6161158427585791488
860 6225635645731817713
861 6290711955187481400
862 6356392220964272964
863 6422681341894204536
864 6489584250832408208
865 6557105914846858183
866 6625251335422892619
867 6694025548654708231
868 6763433625451692329
869 6833480671731765169
870 6904171828629599139
871 6975512272691693885
872 7047507216086558991
873 7120161906801598571
874 7193481628855142207
875 7267471702495215963
876 7342137484413498450
877 7417484367945862322
878 7493517783288333480
879 7570243197699479654
880 7647666115718256542
881 7725792079368321224
882 7804626668377843782
883 7884175500385627752
884 7964444231162965150
885 8045438554821643124
886 8127164204037724327
887 8209626950261518314
888 8292832603943366605
889 8376787014745459165
890 8461496071769704660
891 8546965703771471095
892 8633201879389421335
893 8720210607361258135
894 8807997936755605075
895 8896569957189635335
896 8985932799063078460
897 9076092633777813655
898 9167055673973881465
899 9258828173751121735
900 9351416428907272061
901 9444826777161527876
902 9539065598394809803
903 9634139314875327452
904 9730054391500891962
905 9826817336026566270
906 9924434699309105516
907 10022913075536569344
908 10122259102474973116
909 10222479461699944644
910 10323580878845462409
911 10425570123837639396
912 10528454011145631814
913 10632239400017424585
914 10736933194732994335
915 10842542344842180671
916 10949073845419976805
917 11056534737306571029
918 11164932107364850210
919 11274273088722483169
920 11384564861031722562
921 11495814650713615123
922 11608029731219974283
923 11721217423279802515
924 11835385095163519838
925 11950540162931469872
926 12066690090700490578
927 12183842390894589818
928 12302004624513728735
929 12421184401386752888
930 12541389380442476113
931 12662627269964735960
932 12784905827865865226
933 12908232861943959254
934 13032616230158603585
935 13158063840890440962
936 13284583653219242851
937 13412183677185643845
938 13540871974071646025
939 13670656656664608231
940 13801545889540050676
941 13933547889327987771
942 14066670924998122533
943 14200923318128388679
944 14336313443192623706
945 14472849727831410453
946 14610540653142094285
947 14749394753952013663
948 14889420619110951824
949 15030626891766620080
950 15173022269659635624
951 15316615505401347664
952 15461415406771204792
953 15607430836997015296
954 15754670715054795344
955 15903144015951326144
956 16052859771026574480
957 16203827068238638640
958 16356055052468603688
959 16509552925807967408
960 16664329947866023385
961 16820395436059627617
962 16977758765923202771
963 17136429371400938247
964 17296416745159275009
965 17457730438881633139
966 17620380063583471188
967 17784375289909399845
968 17949725848450910043
969 18116441530045966395
970 18284532186099263358
971 18454007728884392379
972 18624878131866720938
973 18797153430007990954
974 18970843720091915820
975 19145959161031305570
976 19322509974196238189
977 19500506443723807336
978 19679958916848964606
979 19860877804216744328
980 20043273580215873751
981 20227156783293571298
982 20412538016291779883
983 20599427946764635298
984 20787837307317419241
985 20977776895926552251
986 21169257576281364309
987 21362290278106709591
988 21556885997507407775
989 21753055797293578175
990 21950810807327851202
991 22150162224853273227
992 22351121314843386952
993 22553699410332806151
994 22757907912770016001
995 22963758292350717151
996 23171262088373445364
997 23380430909575535164
998 23591276434491659439
999 23803810411792511716
1000 24018044660646115675