0 1
1 3
2 8
3 26
4 69
5 166
6 365
7 750
8 1446
9 2646
10 4645
11 7856
12 12852
13 20411
14 31626
15 47910
16 71022
17 103342
18 147982
19 208554
20 289572
21 397140
22 538319
23 720965
24 955716
25 1255661
26 1634233
27 2108003
28 2699453
29 3431884
30 4329465
31 5426928
32 6764353
33 8377805
34 10314695
35 12640228
36 15412581
37 18691064
38 22570710
39 27149631
40 32504491
41 38754204
42 46058514
43 54533113
44 64306840
45 75610960
46 88643937
47 103543069
48 120586946
49 140114312
50 162310163
51 187444248
52 216026561
53 248388598
54 284753013
55 325742181
56 371979780
57 423694526
58 481460413
59 546297545
60 618640272
61 698857207
62 788267862
63 887850497
64 997791827
65 1119337966
66 1254322057
67 1403098838
68 1566381877
69 1746784882
70 1945537511
71 2162665091
72 2400838627
73 2662961724
74 2948876175
75 3260204045
76 3601702908
77 3974349607
78 4378009666
79 4818132883
80 5298619646
81 5818081334
82 6380364913
83 6993301956
84 7656425225
85 8369953012
86 9144214210
87 9983199578
88 10883459071
89 11853664195
90 12905225709
91 14034128490
92 15242697227
93 16548848689
94 17954240127
95 19452989739
96 21062998076
97 22798370326
98 24648590938
99 26622181939
100 28747245973
101 31018472715
102 33428831997
103 36011840328
104 38780593753
105 41714958835
106 44837392022
107 48187069969
108 51744519803
109 55506457470
110 59529695714
111 63818118360
112 68340392920
113 73145369112
114 78279837563
115 83700935421
116 89420282687
117 95524773106
118 101994963380
119 108791357504
120 116006400313
121 123683191382
122 131746299243
123 140242532224
124 149290541092
125 158827238515
126 168817205739
127 179416255936
128 190640991986
129 202378593140
130 214742463104
131 227873257630
132 241639655644
133 256037500203
134 271302748270
135 287388662687
136 304151593070
137 321813453999
138 340508009677
139 360012167739
140 380400896074
141 401994289146
142 424631755411
143 448166475485
144 472975822146
145 499131274060
146 526305209886
147 554723744256
148 584768549176
149 616106301425
150 648647222891
151 682963604858
152 718978545257
153 756272546169
154 795316866572
155 836489790203
156 879230139520
157 923608703542
158 970403951884
159 1019276183193
160 1069771160281
161 1122709266137
162 1178343961919
163 1235855038799
164 1295626523297
165 1358598217156
166 1424037326102
167 1491577920220
168 1562477891647
169 1636681248683
170 1713129993772
171 1792717932574
172 1876414345725
173 1962972467119
174 2052322876618
175 2146193000116
176 2243976466921
177 2344486450852
178 2449343291380
179 2559300754573
180 2672526013343
181 2789549081885
182 2912489170731
183 3039918557055
184 3170756342377
185 3307537948481
186 3450432601296
187 3597050723763
188 3748908833452
189 3908272614528
190 4072641341323
191 4241433664506
192 4418184905677
193 4602002171479
194 4790132224667
195 4985506348532
196 5190076132228
197 5400108591661
198 5616090040708
199 5842439276781
200 6076666167913
201 6316075661292
202 6565397235995
203 6825573921393
204 7091667062508
205 7365954446904
206 7653316290359
207 7949163884140
208 8251565936989
209 8567255841511
210 8895269442033
211 9229781300253
212 9575667240543
213 9937455453164
214 10308121345386
215 10687512158342
216 11084222472109
217 11494370827681
218 11911963525806
219 12345219046548
220 12797074530354
221 13258057175295
222 13731086225531
223 14225943480192
224 14734869908230
225 15252910588792
226 15792086061323
227 16352128239183
228 16921605897031
229 17507965271036
230 18120818279784
231 18747842406731
232 19386858265591
233 20053574815530
234 20742688086076
235 21441973306441
236 22164788162123
237 22918468667471
238 23685987671232
239 24470161796815
240 25289390917132
241 26131561774114
242 26985636293153
243 27871837782000
244 28792447317899
245 29726425966837
246 30684111064438
247 31684447659018
248 32707172727826
249 33745296416545
250 34825963166760
251 35943204131173
252 37073769545102
253 38237989472677
254 39451931948408
255 40686721443489
256 41943093892282
257 43253758055236
258 44601331541035
259 45963480108185
260 47372387848337
261 48836646830998
262 50319649671429
263 51834087698917
264 53415014254549
265 55031112822698
266 56665520274699
267 58362788426806
268 60118651954021
269 61891425610625
270 63710008538958
271 65606469935389
272 67534399383696
273 69488301920963
274 71523438138266
275 73617226116873
276 75727662958227
277 77903294690300
278 80165875107893
279 82454842120255
280 84782932283438
281 87211533303359
282 89695179905156
283 92198578947976
284 94791426522847
285 97476398925643
286 100182497642328
287 102947760351728
288 105831739612836
289 108763549658102
290 111723788603179
291 114801582260580
292 117971406458001
293 121158822541068
294 124433230974813
295 127841073425473
296 131286703478568
297 134777428282189
298 138415642615812
299 142139637195935
300 145882057714087
301 149747062509786
302 153754173118786
303 157787883979049
304 161893603768233
305 166175573916419
306 170530822714415
307 174912992258049
308 179459774585421
309 184148992324018
310 188855201632991
311 193672165556497
312 198689220873200
313 203761781744389
314 208881088285019
315 214210601549720
316 219672951829778
317 225148077102403
318 230784826144453
319 236636542756271
320 242523023387841
321 248490949867075
322 254713830291630
323 261049594217961
324 267404112283425
325 273981650254744
326 280776329939789
327 287585874048650
328 294529130459908
329 301765601050752
330 309085789053872
331 316446355085554
332 324097964149117
333 331953442576292
334 339810122444243
335 347871290722654
336 356251211400554
337 364679528613317
338 373190922234145
339 382061736840009
340 391106621968437
341 400152150724783
342 409489741941007
343 419152966612598
344 428828333581820
345 438654960248967
346 448901483709407
347 459276933466812
348 469673495524952
349 480461434392021
350 491558623858617
351 502638259205628
352 513964950354573
353 525754741361740
354 537616894220660
355 549549775501750
356 561976464067874
357 574670486876243
358 587333456487075
359 600365395949683
360 613877164474857
361 627400313191466
362 641079941553726
363 655347167984371
364 669815221044778
365 684266206251657
366 699227967571051
367 714652298798151
368 730032831189731
369 745695843558907
370 762017869788920
371 778454459567547
372 794927324811560
373 812061206650791
374 829602092590877
375 847063100738407
376 864972153708707
377 883575335554637
378 902196242792696
379 920956859050134
380 940520889744507
381 960398226067084
382 980194493096576
383 1000636738754125
384 1021760001830455
385 1042807279208196
386 1064155042317263
387 1086421136454528
388 1108874349414665
389 1131297182736538
390 1154581617790559
391 1178478043939967
392 1202225952294802
393 1226493548731286
394 1251746332860938
395 1277039294499241
396 1302420470317416
397 1328874653823752
398 1355814370881887
399 1382575926128643
400 1410127156328506
401 1438663941444865
402 1467091257284557
403 1495805274835889
404 1525772099555986
405 1556046656634762
406 1586180141400862
407 1617405998027909
408 1649538271735770
409 1681432860405203
410 1713896821734300
411 1747732087712294
412 1781660504376146
413 1815574985165906
414 1850888612365820
415 1886945301710990
416 1922686910759964
417 1959357654883217
418 1997429146552233
419 2035365762124646
420 2073524496435443
421 2113355976157030
422 2153688674032571
423 2193712576127529
424 2235081200008880
425 2277769821368079
426 2320113889828041
427 2363034606519097
428 2407826642489893
429 2452817000234223
430 2497621664832533
431 2544206172694579
432 2591909493408478
433 2639116151817624
434 2687367555989457
435 2737573076528064
436 2787642530029764
437 2837794765398897
438 2890132107122774
439 2943270526082920
440 2995862282910275
441 3050056769734457
442 3106139275702899
443 3161761089742849
444 3217897185631174
445 3276536190525212
446 3335561906282052
447 3394139192789724
448 3454922581128888
449 3517359765553950
450 3579073022571072
451 3641894836803369
452 3707391515460801
453 3772800494262267
454 3838049318874239
455 3906089211878873
456 3975380097311105
457 4043804695693245
458 4114070401772860
459 4186986840110295
460 4259333814312522
461 4332028456844430
462 4408003300934270
463 4484679038183465
464 4560530001972809
465 4639040291685261
466 4719947945395882
467 4799864084652093
468 4880863193692339
469 4965454135995432
470 5050092635538006
471 5134191277990000
472 5221772965184116
473 5311260702796579
474 5399472961541803
475 5489708339250889
476 5583595679580292
477 5676840149312862
478 5770119288429481
479 5867609075475402
480 5966296046957661
481 6063646273586247
482 6164104988998406
483 6267970471007692
484 6370551538446201
485 6474052329886385
486 6582283687587705
487 6690837099548823
488 6798297941121586
489 6909999995164768
490 7024535498934123
491 7137295882774302
492 7252154897952752
493 7371950665201584
494 7491108536924326
495 7609792472568330
496 7733767556073735
497 7859690218010993
498 7983609850977442
499 8111036691376830
500 8243209291331032
501 8373807917688141
502 8504965931746312
503 8642233337388518
504 8780306999194198
505 8916525150244908
506 9057772967047222
507 9203133190531801
508 9346138265527785
509 9491145836253807
510 9642701259966380
511 9793764230395938
512 9943594012238913
513 10099927274025760
514 10259301683642507
515 10415840838990584
516 10576170910833232
517 10742982989423082
518 10907981877179794
519 11072912327297217
520 11245577268578247
521 11419833866242210
522 11591226738699516
523 11768411978046542
524 11951430154618503
525 12131458745019124
526 12313140827549279
527 12503343851757240
528 12693425752613204
529 12881205998116614
530 13076795402925579
531 13276969365019645
532 13473310185746132
533 13673525390292939
534 13882423631626696
535 14089390459749499
536 14295313342735799
537 14510830219612690
538 14729140268367662
539 14943304590600492
540 15163918043532963
541 15392624672926105
542 15617700689960616
543 15843730818378188
544 16080639423835586
545 16318137078392233
546 16551896849493938
547 16794800544625716
548 17044405524145694
549 17289032070883419
550 17537308472859710
551 17796995428043243
552 18054853769120854
553 18310257388047812
554 18577312226223571
555 18848917664402816
556 19114805363689604
557 19387585000564268
558 19671359544651658
559 19950932323229313
560 20230296573304941
561 20523283038762191
562 20818051810845579
563 21107225208159990
564 21406810738139890
565 21715925379206655
566 22018812452710826
567 22324685682975711
568 22645271878109021
569 22964488520013468
570 23279313313138982
571 23607975403116851
572 23943666134875297
573 24271780449687791
574 24606876690251250
575 24956609938844309
576 25301752733951791
577 25644935217297181
578 26004842198147194
579 26368386178658086
580 26724014288707860
581 27091123831904935
582 27471448819194080
583 27844270657721070
584 28218821613403090
585 28611988668416989
586 29004777486345809
587 29390622082698118
588 29792510170738749
589 30204813198398868
590 30607426270102651
591 31016586804020046
592 31444853941004146
593 31868480998769092
594 32287672088687722
595 32726981725301171
596 33172658244654734
597 33607614004873494
598 34054747897600611
599 34519791846145509
600 34976151431109300
601 35432214715121044
602 35911390185942178
603 36391932424198587
604 36862283823452157
605 37350748890434608
606 37854129508748534
607 38345522532402776
608 38842299289494794
609 39363543850052288
610 39880646178622872
611 40389975712351007
612 40922993396953745
613 41466231288854672
614 41995468710157542
615 42536989887128976
616 43102265975473354
617 43657945407282796
618 44210343080740896
619 44790888105341666
620 45375568609606653
621 45946058304117766
622 46536385414995097
623 47147459823484869
624 47744186602959275
625 48344167709063443
626 48974896887821663
627 49602796512956944
628 50218594196583143
629 50861649118445262
630 51520179914181056
631 52161008912816193
632 52813371242242921
633 53496604435621755
634 54169836506086870
635 54835639797682400
636 55535051100199208
637 56242709703898296
638 56931397418783478
639 57641029587421542
640 58378788243578739
641 59099962690224206
642 59821032428734592
643 60580024591059168
644 61338646696457311
645 62079731851941464
646 62851396989383438
647 63645498021741550
648 64417885852007711
649 65199889657998145
650 66021234625478241
651 66832995315149391
652 67631816927661189
653 68469945310019260
654 69322142243420772
655 70149828760671983
656 70998616226568893
657 71884657343915835
658 72752265076040505
659 73614894987857303
660 74523420761659599
661 75435582696035707
662 76323585328823962
663 77244920139666550
664 78197668415806610
665 79124568355494395
666 80057646676522053
667 81039916909096573
668 82014238082321932
669 82968557647877431
670 83967845761273813
671 84989139649203147
672 85979709895487453
673 86990188624411803
674 88048961444153440
675 89088195186471211
676 90115769464983023
677 91197828448620228
678 92289544150049018
679 93349259076049489
680 94444078724562360
681 95581614427059064
682 96689321940947316
683 97797861247907760
684 98966770448656466
685 100131071515769116
686 101266596571515635
687 102452339485114408
688 103670576268699320
689 104851373471895535
690 106049077046724796
691 107308134905080241
692 108547752857018676
693 109766931116068667
694 111049507018742295
695 112350304989943365
696 113610080438082151
697 114905255949609182
698 116257054585246518
699 117575590674006424
700 118887289842973940
701 120271707392808082
702 121657144174220593
703 123003208755648385
704 124403841590961801
705 125850452596774817
706 127252683844413474
707 128666493176155863
708 130156756974468331
709 131629462721597320
710 133070583022901002
711 134583920935276209
712 136127173540199759
713 137619335233974593
714 139145129452621187
715 140744282025386363
716 142307802858732727
717 143854074142248205
718 145486297341901465
719 147128125828222722
720 148718128407132125
721 150365546040264942
722 152075853475644737
723 153735026433479785
724 155397561866251188
725 157153595343022790
726 158896437241599628
727 160593961958259423
728 162371872395652572
729 164195133990347643
730 165956445195110592
731 167746889804130647
732 169630390969690678
733 171477622211861545
734 173294037762651005
735 175210084595688237
736 177148036788430334
737 179019918814057097
738 180949833315656274
739 182963361742602025
740 184919751608752497
741 186867811992064865
742 188928111198412023
743 190982898491953427
744 192975905156870004
745 195056100473937367
746 197201451793973097
747 199273609183875029
748 201366928300031652
749 203575973285759539
750 205750666761862923
751 207877453925441385
752 210117381243178201
753 212396049833432124
754 214592815562661060
755 216845157598246432
756 219205950475925199
757 221505095456531338
758 223780148592714096
759 226187449175559378
760 228601181437128196
761 230933900182566678
762 233358369866680921
763 235872766232045839
764 238302930675456112
765 240742016612368532
766 243322308775315522
767 245873718317355349
768 248356306423895713
769 250964559668612413
770 253633788032324703
771 256204065644724999
772 258823436456372559
773 261580377674407838
774 264273600383698393
775 266922328910840605
776 269723936183829590
777 272549242065505377
778 275271640605179776
779 278087072750200517
780 281022694079291679
781 283864054560896676
782 286697001242750070
783 289699073487508873
784 292682445969047412
785 295572066724396305
786 298597868513039363
787 301713142449381791
788 304711785617498977
789 307747966417920283
790 310955107886823283
791 314100059119452488
792 317174965353392776
793 320423113634356281
794 323718694410613830
795 326887110745685899
796 330145367625106403
797 333559969027236477
798 336872336921812874
799 340153036096819979
800 343632590965387437
801 347109667727469922
802 350464010537344073
803 353961796542043856
804 357584634436734939
805 361073362553011124
806 364581888145441692
807 368298785979635862
808 371960006301270460
809 375520078838150672
810 379272328081149561
811 383103401179509882
812 386781223310533050
813 390539879358808124
814 394497142235421067
815 398347572038006318
816 402136376876928044
817 406154651911862031
818 410194175058140271
819 414078097729036981
820 418108009225585094
821 422306347961140506
822 426354422108713619
823 430397225265912830
824 434689288883647874
825 438938782474348277
826 443050226460753476
827 447369905716508117
828 451808643437293090
829 456067034311856236
830 460389984949464128
831 464959870090324305
832 469423301521564024
833 473787761384173588
834 478411928288361687
835 483090145762889347
836 487576440010998762
837 492204883140012309
838 497053458165817520
839 501738388666269099
840 506384521238016165
841 511323381778588991
842 516241195997171979
843 520978227925523790
844 525934936518978336
845 531060895557835682
846 535979560265722485
847 540937709827821722
848 546196815942404203
849 551356731123784082
850 556372400244822755
851 561676008318807912
852 567077171380515410
853 572247381432358971
854 577547663566441492
855 583128383125304471
856 588536663121234133
857 593863098982233033
858 599527005744186590
859 605201809033764957
860 610647515735258578
861 616317694139811782
862 622218232437224703
863 627886223279916330
864 633558259792560208
865 639590193256194831
866 645539281432364206
867 651290603043981789
868 657354079249247464
869 663570926050023350
870 669516217304660652
871 675569270901687659
872 681971586491626676
873 688199444567049741
874 694291968366181203
875 700766224410489349
876 707295874531791286
877 713543134730399155
878 720010717836595991
879 726781396769790482
880 733297950285657849
881 739771213955233485
882 746666978229345813
883 753507799369151057
884 760089065369797355
885 767000285003247288
886 774134504591798511
887 780956577810501037
888 787851781725687521
889 795173059441986388
890 802327222801896117
891 809281407045594063
892 816658857560757123
893 824150951845457867
894 831303417196961506
895 838660582937194543
896 846405554989881742
897 853880953335286740
898 861252404370834128
899 869110820493889837
900 876956458119166164
901 884472842849266149
902 892327786075974588
903 900490458403446480
904 908302503198208796
905 916138610585269540
906 924484511014011656
907 932682969292969768
908 940605240628075563
909 948986829958129248
910 957559229477293929
911 965732360407497091
912 974080386470045958
913 982912771261929870
914 991469218582576017
915 999846508367794813
916 1008774680987352247
917 1017749373875942213
918 1026318038892798680
919 1035221549132191713
920 1044533558627035046
921 1053461238142819692
922 1062347418776811748
923 1071832296534723019
924 1081205054961011718
925 1090213848665985652
926 1099709263871591400
927 1109490584284896204
928 1118812734116515176
929 1128262974745265764
930 1138305229637402295
931 1148077732285690078
932 1157580379984496365
933 1167694226452423899
934 1177933968587687196
935 1187685233547858907
936 1197751893835530591
937 1208344316903989456
938 1218526773558273474
939 1228583776662459100
940 1239331114390339534
941 1250020923904126498
942 1260247923601065359
943 1270976343873111785
944 1282106407406128058
945 1292719946220511129
946 1303394939813806635
947 1314779235182590996
948 1325916472920221016
949 1336677147389002757
950 1348102010268847752
951 1359755108751690160
952 1370833681567300260
953 1382188824474927572
954 1394203294861714897
955 1405794164880938119
956 1417155606358705957
957 1429298501821398695
958 1441461552973585432
959 1453053010474146609
960 1465143982477408881
961 1477774228082651312
962 1489836695514468919
963 1501871411887783382
964 1514740025497089017
965 1527405199259334764
966 1539571103723931654
967 1552442469422966322
968 1565670051241593188
969 1578236308505537543
970 1591017174004391401
971 1604606234240166541
972 1617774656613388939
973 1630588432015830695
974 1644270160736382081
975 1658076727958317794
976 1671194855967492053
977 1684789315119774536
978 1699083167487950121
979 1712768441226045053
980 1726311675003504975
981 1740817424560985143
982 1755189065075663845
983 1768923419485958527
984 1783387767384878636
985 1798364228140014824
986 1812595534386778479
987 1826952588173316520
988 1842280040258914810
989 1857211643712857546
990 1871641465385884798
991 1887016144692903602
992 1902651168048229376
993 1917475596135605681
994 1932727052861624089
995 1948860255553513534
996 1964359719790180241
997 1979575633477099471
998 1995882371239765914
999 2012155091956046075
1000 2027638705314438969