0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 41
11 54
12 73
13 94
14 123
15 157
16 201
17 252
18 318
19 393
20 488
21 598
22 732
23 887
24 1076
25 1291
26 1549
27 1845
28 2194
29 2592
30 3060
31 3589
32 4206
33 4904
34 5708
35 6615
36 7658
37 8825
38 10158
39 11651
40 13343
41 15231
42 17365
43 19735
44 22402
45 25361
46 28670
47 32332
48 36420
49 40925
50 45935
51 51451
52 57559
53 64267
54 71680
55 79796
56 88740
57 98520
58 109259
59 120979
60 133827
61 147811
62 163103
63 179729
64 197860
65 217536
66 238959
67 262158
68 287367
69 314633
70 344192
71 376114
72 410673
73 447924
74 488181
75 531528
76 578283
77 628555
78 682709
79 740845
80 803377
81 870436
82 942444
83 1019570
84 1102294
85 1190772
86 1285544
87 1386811
88 1495127
89 1610734
90 1734256
91 1865931
92 2006456
93 2156119
94 2315637
95 2485356
96 2666077
97 2858141
98 3062437
99 3279374
100 3509869
101 3754396
102 4013973
103 4289081
104 4580843
105 4889816
106 5217162
107 5563524
108 5930184
109 6317793
110 6727758
111 7160830
112 7618467
113 8101517
114 8611579
115 9149527
116 9717107
117 10315305
118 10945933
119 11610102
120 12309790
121 13046138
122 13821297
123 14636550
124 15494132
125 16395466
126 17342981
127 18338153
128 19383613
129 20480997
130 21633040
131 22841553
132 24109496
133 25438744
134 26832491
135 28292809
136 29823020
137 31425393
138 33103511
139 34859736
140 36697922
141 38620652
142 40631936
143 42734597
144 44932945
145 47229912
146 49630120
147 52136769
148 54754668
149 57487286
150 60339776
151 63315755
152 66420733
153 69658627
154 73035170
155 76554601
156 80223046
157 84044915
158 88026742
159 92173293
160 96491366
161 100986087
162 105664701
163 110532553
164 115597352
165 120864841
166 126343038
167 132038110
168 137958582
169 144110873
170 150504033
171 157144947
172 164043025
173 171205625
174 178642730
175 186362009
176 194374038
177 202687004
178 211311901
179 220257465
180 229535335
181 239154601
182 249127570
183 259463932
184 270176474
185 281275496
186 292774509
187 304684240
188 317018949
189 329790028
190 343012287
191 356697819
192 370862245
193 385518140
194 400681963
195 416367050
196 432590488
197 449366388
198 466712742
199 484644230
200 503179779
201 522334910
202 542129262
203 562579239
204 583705487
205 605525049
206 628059611
207 651327170
208 675350217
209 700147722
210 725743295
211 752156648
212 779412545
213 807531748
214 836539928
215 866458945
216 897315709
217 929132908
218 961938730
219 995757045
220 1030617058
221 1066543845
222 1103567980
223 1141715490
224 1181018360
225 1221503913
226 1263205271
227 1306151109
228 1350376059
229 1395909850
230 1442788669
231 1491043694
232 1540712380
233 1591827384
234 1644427822
235 1698547548
236 1754227388
237 1811502780
238 1870415959
239 1931004010
240 1993310991
241 2057375309
242 2123242898
243 2190953925
244 2260555885
245 2332090742
246 2405607989
247 2481151077
248 2558771554
249 2638514788
250 2720434053
251 2804576706
252 2890998206
253 2979747544
254 3070882425
255 3164453959
256 3260521753
257 3359139080
258 3460367932
259 3564263408
260 3670889950
261 3780304958
262 3892574966
263 4007759757
264 4125928464
265 4247142867
266 4371474768
267 4498988477
268 4629758092
269 4763850506
270 4901342644
271 5042303615
272 5186813246
273 5334943387
274 5486776378
275 5642386901
276 5801860366
277 5965273871
278 6132715976
279 6304266779
280 6480017586
281 6660051557
282 6844463327
283 7033338721
284 7226775788
285 7424863593
286 7627703180
287 7835386957
288 8048019572
289 8265696327
290 8488525565
291 8716606121
292 8950049597
293 9188958433
294 9433448127
295 9683624296
296 9939606430
297 10201503952
298 10469439893
299 10743527597
300 11023894301
301 11310656788
302 11603946603
303 11903884663
304 12210606354
305 12524236810
306 12844915951
307 13172772668
308 13507951524
309 13850585853
310 14200824376
311 14558804998
312 14924681321
313 15298595306
314 15680705551
315 16071158827
316 16470118227
317 16877735427
318 17294178769
319 17719604341
320 18154185855
321 18598084556
322 19051479009
323 19514535758
324 19987439004
325 20470360040
326 20963488832
327 21467002239
328 21981095457
329 22505951019
330 23041770166
331 23588740579
332 24147069680
333 24716951105
334 25298597905
335 25892209828
336 26498006402
337 27116192901
338 27746995473
339 28390625800
340 29047316081
341 29717284528
342 30400770271
343 31097997492
344 31809212403
345 32534646028
346 33274551074
347 34029165580
348 34798749662
349 35583547753
350 36383827537
351 37199840790
352 38031862159
353 38880150901
354 39744989575
355 40626644323
356 41525405783
357 42441547922
358 43375368835
359 44327150504
360 45297199464
361 46285805054
362 47293282425
363 48319929294
364 49366068787
365 50432007152
366 51518076509
367 52624591007
368 53751891945
369 54900302383
370 56070172140
371 57261833396
372 58475645546
373 59711949194
374 60971113505
375 62253488601
376 63559452740
377 64889365733
378 66243616024
379 67622572446
380 69026633832
381 70456179122
382 71911616842
383 73393336267
384 74901756747
385 76437277159
386 78000327890
387 79591318589
388 81210689966
389 82858862632
390 84536288790
391 86243399309
392 87980658108
393 89748507475
394 91547422312
395 93377856575
396 95240297358
397 97135209513
398 99063092560
399 101024423498
400 103019713520
401 105049451981
402 107114162997
403 109214347539
404 111350542890
405 113523262877
406 115733057179
407 117980452750
408 120266012956
409 122590277067
410 124953822391
411 127357201847
412 129801005895
413 132285801334
414 134812193108
415 137380761117
416 139992125056
417 142646879250
418 145345657335
419 148089068355
420 150877761262
421 153712358969
422 156593526022
423 159521900622
424 162498162080
425 165522964138
426 168597002291
427 171720945005
428 174895504249
429 178121364622
430 181399253719
431 184729872591
432 188113965921
433 191552250322
434 195045487868
435 198594412242
436 202199802040
437 205862408292
438 209583027624
439 213362427558
440 217201423065
441 221100799657
442 225061389762
443 229083997227
444 233169473491
445 237318639805
446 241532366947
447 245811495172
448 250156913690
449 254569482062
450 259050109529
451 263599674064
452 268219105281
453 272909301156
454 277671210748
455 282505752408
456 287413896287
457 292396580140
458 297454795566
459 302589501419
460 307801709798
461 313092400985
462 318462609275
463 323913335444
464 329445636352
465 335060534955
466 340759109711
467 346542406157
468 352411526093
469 358367536625
470 364411563279
471 370544696524
472 376768084624
473 383082841768
474 389490140752
475 395991118512
476 402586972775
477 409278865008
478 416068016861
479 422955614764
480 429942906135
481 437031101313
482 444221473898
483 451515260034
484 458913758475
485 466418231556
486 474030005081
487 481750366563
488 489580669286
489 497522227828
490 505576421904
491 513744593620
492 522028151070
493 530428462794
494 538946965711
495 547585056795
496 556344200721
497 565225823315
498 574231419010
499 583362441430
500 592620415228
501 602006823818
502 611523220984
503 621171120427
504 630952107117
505 640867723905
506 650919587426
507 661109271791
508 671438424190
509 681908650444
510 692521630408
511 703279000520
512 714182473796
513 725233719391
514 736434482352
515 747786465083
516 759291446828
517 770951162061
518 782767424737
519 794742003621
520 806876746228
521 819173456099
522 831634016531
523 844260264707
524 857054120238
525 870017456162
526 883152227232
527 896460342909
528 909943795368
529 923604529273
530 937444574771
531 951465914065
532 965670614082
533 980060695085
534 994638263119
535 1009405375332
536 1024364177456
537 1039516765852
538 1054865324727
539 1070411990262
540 1086158987535
541 1102108491284
542 1118262768047
543 1134624033575
544 1151194594632
545 1167976708540
546 1184972724746
547 1202184940928
548 1219615749824
549 1237267491915
550 1255142601976
551 1273243463938
552 1291572557131
553 1310132307631
554 1328925239951
555 1347953824889
556 1367220630867
557 1386728174003
558 1406479069207
559 1426475876661
560 1446721258412
561 1467217821276
562 1487968273141
563 1508975268146
564 1530241562662
565 1551769856804
566 1573562956096
567 1595623609332
568 1617954669873
569 1640558935831
570 1663439311110
571 1686598641843
572 1710039883168
573 1733765931935
574 1757779793180
575 1782084415202
576 1806682855704
577 1831578113045
578 1856773298309
579 1882271462748
580 1908075769469
581 1934189323299
582 1960615342203
583 1987356983246
584 2014417519987
585 2041800164554
586 2069508244722
587 2097545028460
588 2125913900661
589 2154618183703
590 2183661320355
591 2213046690370
592 2242777792995
593 2272858066085
594 2303291068333
595 2334080294318
596 2365229362961
597 2396741828524
598 2428621368737
599 2460871598370
600 2493496256998
601 2526499018426
602 2559883684880
603 2593653992302
604 2627813804129
605 2662366919214
606 2697317265311
607 2732668702765
608 2768425224477
609 2804590755380
610 2841169352062
611 2878165004918
612 2915581837398
613 2953423903844
614 2991695395423
615 3030400433667
616 3069543275979
617 3109128111903
618 3149159268324
619 3189641001340
620 3230577708198
621 3271973714786
622 3313833487212
623 3356161422080
624 3398962057677
625 3442239859765
626 3485999439716
627 3530245335837
628 3574982231064
629 3620214737122
630 3665947611901
631 3712185539045
632 3758933352330
633 3806195810701
634 3853977822278
635 3902284222285
636 3951119996650
637 4000490055278
638 4050399462864
639 4100853207528
640 4151856431170
641 4203414201051
642 4255531739815
643 4308214192325
644 4361466862955
645 4415294977699
646 4469703921079
647 4524699001254
648 4580285686508
649 4636469365525
650 4693255591365
651 4750649836924
652 4808657738435
653 4867284853986
654 4926536906674
655 4986419538201
656 5046938559570
657 5108099699778
658 5169908856112
659 5232371845955
660 5295494656646
661 5359283192273
662 5423743531298
663 5488881668356
664 5554703771390
665 5621215926619
666 5688424395313
667 5756335353657
668 5824955157349
669 5894290076378
670 5964346559207
671 6035130970779
672 6106649856248
673 6178909673790
674 6251917066380
675 6325678589428
676 6400200982048
677 6475490897980
678 6551555176484
679 6628400567973
680 6706034013013
681 6784462362687
682 6863692657166
683 6943731849415
684 7024587083297
685 7106265411897
686 7188774083962
687 7272120256862
688 7356311282506
689 7441354423706
690 7527257139703
691 7614026797056
692 7701670963561
693 7790197113685
694 7879612922038
695 7969925972270
696 8061144050059
697 8153274846436
698 8246326259402
699 8340306091701
700 8435222351897
701 8531082955667
702 8627896026475
703 8725669591198
704 8824411889488
705 8924131063751
706 9024835468047
707 9126533361652
708 9229233217457
709 9332943409767
710 9437672531625
711 9543429076868
712 9650221756892
713 9758059186352
714 9866950199507
715 9976903530058
716 10087928136481
717 10200032876024
718 10313226829563
719 10427518979302
720 10542918533113
721 10659434596276
722 10777076505048
723 10895853492464
724 11015775021329
725 11136850453786
726 11259089383873
727 11382501301033
728 11507095931961
729 11632882898076
730 11759872056874
731 11888073163230
732 12017496210216
733 12148151084244
734 12280047915421
735 12413196726554
736 12547607782911
737 12683291245117
738 12820257518466
739 12958516899556
740 13098079935202
741 13238957062832
742 13381158968889
743 13524696233183
744 13669579686741
745 13815820049799
746 13963428299500
747 14112415301547
748 14262792177288
749 14414569939389
750 14567759858452
751 14722373092224
752 14878421062130
753 15035915076039
754 15194866704270
755 15355287406441
756 15517188906907
757 15680582815041
758 15845481010841
759 16011895258665
760 16179837592206
761 16349319932377
762 16520354471803
763 16692953286036
764 16867128728278
765 17042893033948
766 17220258714860
767 17399238168005
768 17579844069142
769 17762088974803
770 17945985726376
771 18131547045355
772 18318785936774
773 18507715288737
774 18698348275353
775 18890697949384
776 19084777655738
777 19280600617257
778 19478180347647
779 19677530241614
780 19878663987189
781 20081595148876
782 20286337590795
783 20492905052865
784 20701311573277
785 20911571069092
786 21123697758198
787 21337705732812
788 21553609392324
789 21771423009725
790 21991161163872
791 22212838310397
792 22436469213349
793 22662068508899
794 22889651148135
795 23119231953585
796 23350826061323
797 23584448482043
798 23820114542632
799 24057839439931
800 24297638693528
801 24539527692230
802 24783522146257
803 25029637638334
804 25277890075242
805 25528295231487
806 25780869212342
807 26035627990116
808 26292587866489
809 26551765013467
810 26813175935168
811 27076837001243
812 27342764920223
813 27610976265429
814 27881487947702
815 28154316746072
816 28429479779826
817 28706994031533
818 28986876830945
819 29269145370401
820 29553817187999
821 29840909687829
822 30130440622577
823 30422427606000
824 30716888607435
825 31013841456540
826 31313304337169
827 31615295297010
828 31919832740781
829 32226934931997
830 32536620498349
831 32848907925624
832 33163816062335
833 33481363618612
834 33801569670245
835 34124453149592
836 34450033361875
837 34778329468128
838 35109361000839
839 35443147351940
840 35779708287749
841 36119063428860
842 36461232777622
843 36806236189954
844 37154093902055
845 37504826007332
846 37858452982507
847 38214995156330
848 38574473248295
849 38936907829162
850 39302319859000
851 39670730152896
852 40042159918278
853 40416630212294
854 40794162492028
855 41174778063573
856 41558498631457
857 41945345752977
858 42335341387002
859 42728507339858
860 43124865827100
861 43524438910973
862 43927249061492
863 44333318599236
864 44742670255689
865 45155326607467
866 45571310649918
867 45990645222807
868 46413353583105
869 46839458836082
870 47268984507455
871 47701953965797
872 48138391008016
873 48578319273105
874 49021762826908
875 49468745581354
876 49919291878462
877 50373425900770
878 50831172268968
879 51292555443546
880 51757600321596
881 52226331644017
882 52698774591658
883 53174954183597
884 53654895886987
885 54138625006435
886 54626167293115
887 55117548339782
888 55612794189104
889 56111930719630
890 56614984268121
891 57121981006498
892 57632947563319
893 58147910406438
894 58666896463802
895 59189932496941
896 59717045735843
897 60248263243300
898 60783612549032
899 61323121019819
900 61866816492824
901 62414726636433
902 62966879597958
903 63523303355211
904 64084026363330
905 64649076912219
906 65218483772675
907 65792275544413
908 66370481316649
909 66953130006736
910 67540251019974
911 68131873594189
912 68728027458720
913 69328742169458
914 69934047782596
915 70543974180154
916 71158551742832
917 71777810681555
918 72401781709608
919 73030495364515
920 73663982695017
921 74302274573311
922 74945402381234
923 75593397328603
924 76246291138554
925 76904115356091
926 77566902048576
927 78234683104514
928 78907490933122
929 79585357769294
930 80268316372431
931 80956399321487
932 81649639729031
933 82348070526401
934 83051725176952
935 83760636967468
936 84474839720545
937 85194367075956
938 85919253218581
939 86649532149751
940 87385238414235
941 88126406377925
942 88873070954063
943 89625266870752
944 90383029412808
945 91146393679124
946 91915395323685
947 92690069819354
948 93470453197999
949 94256581303973
950 95048490550187
951 95846217161312
952 96649797928887
953 97459269461022
954 98274668936727
955 99096033345180
956 99923400256083
957 100756807048522
958 101596291680465
959 102441891924207
960 103293646134957
961 104151592475718
962 105015769702222
963 105886216377272
964 106762971654687
965 107646074500312
966 108535564475162
967 109431480945733
968 110333863883579
969 111242753064952
970 112158188869500
971 113080211486656
972 114008861713404
973 114944180149837
974 115886208013681
975 116834986325050
976 117790556719957
977 118752960641903
978 119722240154566
979 120698437122426
980 121681594040295
981 122671753203006
982 123668957534041
983 124673249762139
984 125684673248967
985 126703271154629
986 127729087282510
987 128762165233714
988 129802549250872
989 130850283379581
990 131905412311370
991 132967980533904
992 134038033191208
993 135115615222665
994 136200772222315
995 137293549584941
996 138393993364389
997 139502149408285
998 140618064233945
999 141741784151751
1000 142873356140000