0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 2
10 3
11 4
12 4
13 5
14 5
15 6
16 7
17 8
18 9
19 10
20 11
21 12
22 14
23 16
24 18
25 20
26 22
27 24
28 27
29 30
30 34
31 37
32 40
33 44
34 49
35 54
36 60
37 65
38 71
39 78
40 85
41 94
42 103
43 112
44 122
45 132
46 144
47 158
48 172
49 186
50 201
51 218
52 237
53 258
54 279
55 302
56 326
57 352
58 381
59 412
60 445
61 480
62 516
63 556
64 599
65 646
66 696
67 748
68 803
69 862
70 927
71 996
72 1070
73 1147
74 1228
75 1316
76 1411
77 1512
78 1620
79 1732
80 1852
81 1980
82 2117
83 2264
84 2420
85 2584
86 2757
87 2941
88 3138
89 3350
90 3572
91 3806
92 4053
93 4316
94 4598
95 4898
96 5213
97 5546
98 5897
99 6270
100 6667
101 7088
102 7532
103 8000
104 8493
105 9016
106 9572
107 10160
108 10781
109 11434
110 12122
111 12850
112 13622
113 14438
114 15298
115 16202
116 17154
117 18160
118 19225
119 20348
120 21532
121 22775
122 24084
123 25466
124 26923
125 28462
126 30081
127 31780
128 33568
129 35450
130 37436
131 39530
132 41728
133 44036
134 46461
135 49014
136 51704
137 54534
138 57504
139 60622
140 63896
141 67338
142 70959
143 74764
144 78757
145 82946
146 87339
147 91954
148 96804
149 101896
150 107237
151 112834
152 118701
153 124858
154 131323
155 138104
156 145212
157 152654
158 160451
159 168628
160 177204
161 186192
162 195606
163 205458
164 215775
165 226584
166 237909
167 249772
168 262189
169 275176
170 288766
171 302991
172 317885
173 333478
174 349782
175 366828
176 384653
177 403300
178 422813
179 443220
180 464548
181 486837
182 510128
183 534478
184 559936
185 586544
186 614339
187 643368
188 673686
189 705360
190 738456
191 773024
192 809116
193 846788
194 886110
195 927168
196 970040
197 1014792
198 1061492
199 1110208
200 1161034
201 1214072
202 1269419
203 1327160
204 1387382
205 1450174
206 1515653
207 1583942
208 1655159
209 1729422
210 1806835
211 1887512
212 1971597
213 2059240
214 2150597
215 2245812
216 2345010
217 2448344
218 2555990
219 2668138
220 2784979
221 2906686
222 3033424
223 3165392
224 3302800
225 3445884
226 3594878
227 3749998
228 3911465
229 4079516
230 4254413
231 4436450
232 4625913
233 4823078
234 5028219
235 5241630
236 5463638
237 5694602
238 5934881
239 6184812
240 6444744
241 6715036
242 6996099
243 7288376
244 7592300
245 7908298
246 8236802
247 8578260
248 8933185
249 9302108
250 9685568
251 10084100
252 10498235
253 10928533
254 11375617
255 11840142
256 12322775
257 12824180
258 13345000
259 13885942
260 14447770
261 15031286
262 15637314
263 16266656
264 16920121
265 17598588
266 18302979
267 19034284
268 19793504
269 20581630
270 21399674
271 22248702
272 23129849
273 24044324
274 24993355
275 25978160
276 26999985
277 28060132
278 29159996
279 30301052
280 31484799
281 32712730
282 33986376
283 35307331
284 36677305
285 38098096
286 39571524
287 41099420
288 42683666
289 44326208
290 46029140
291 47794636
292 49624911
293 51522226
294 53488861
295 55527204
296 57639795
297 59829272
298 62098354
299 64449782
300 66886332
301 69410928
302 72026651
303 74736718
304 77544421
305 80453088
306 83466110
307 86587056
308 89819656
309 93167806
310 96635503
311 100226784
312 103945796
313 107796860
314 111784492
315 115913422
316 120188482
317 124614580
318 129196753
319 133940226
320 138850481
321 143933230
322 149194324
323 154639704
324 160275478
325 166107970
326 172143814
327 178389910
328 184853314
329 191541222
330 198461026
331 205620372
332 213027280
333 220690052
334 228617205
335 236817452
336 245299706
337 254073205
338 263147611
339 272532922
340 282239421
341 292277610
342 302658218
343 313392414
344 324491819
345 335968474
346 347834754
347 360103278
348 372787000
349 385899374
350 399454357
351 413466424
352 427950435
353 442921580
354 458395460
355 474388234
356 490916663
357 507998124
358 525650465
359 543891924
360 562741259
361 582217846
362 602341806
363 623133978
364 644615749
365 666809008
366 689736252
367 713420714
368 737886523
369 763158620
370 789262613
371 816224728
372 844071930
373 872832048
374 902533960
375 933207484
376 964883240
377 997592652
378 1031367963
379 1066242468
380 1102250683
381 1139428214
382 1177811690
383 1217438650
384 1258347606
385 1300578376
386 1344172149
387 1389171442
388 1435619962
389 1483562492
390 1533045039
391 1584115132
392 1636821872
393 1691215950
394 1747349460
395 1805275804
396 1865049875
397 1926728300
398 1990369571
399 2056034064
400 2123783812
401 2193682428
402 2265795295
403 2340189818
404 2416935619
405 2496104522
406 2577770317
407 2662008680
408 2748897414
409 2838516666
410 2930949231
411 3026280454
412 3124597994
413 3225991818
414 3330554380
415 3438380914
416 3549569749
417 3664222164
418 3782442236
419 3904336800
420 4030015595
421 4159591650
422 4293181599
423 4430905557
424 4572886974
425 4719252556
426 4870132392
427 5025660542
428 5185975221
429 5351218746
430 5521537384
431 5697081190
432 5878004331
433 6064465611
434 6256628625
435 6454661848
436 6658738360
437 6869035784
438 7085736621
439 7309028730
440 7539105621
441 7776166512
442 8020416069
443 8272064320
444 8531327056
445 8798426310
446 9073590761
447 9357055780
448 9649063122
449 9949860896
450 10259704002
451 10578854628
452 10907582788
453 11246166276
454 11594890386
455 11954047956
456 12323939790
457 12704875234
458 13097172785
459 13501159978
460 13917173212
461 14345557828
462 14786668426
463 15240869670
464 15708536860
465 16190055878
466 16685823082
467 17196245260
468 17721740070
469 18262737018
470 18819677957
471 19393017144
472 19983221089
473 20590768530
474 21216151025
475 21859873992
476 22522457148
477 23204434756
478 23906355426
479 24628782110
480 25372292877
481 26137481838
482 26924959824
483 27735354688
484 28569311015
485 29427490266
486 30310571558
487 31219252694
488 32154251037
489 33116303748
490 34106167582
491 35124619024
492 36172455250
493 37250495192
494 38359580607
495 39500576298
496 40674369899
497 41881872240
498 43124018274
499 44401768314
500 45716109266
501 47068054764
502 48458645207
503 49888948140
504 51360059155
505 52873103456
506 54429237113
507 56029647348
508 57675552669
509 59368203198
510 61108881726
511 62898905648
512 64739628143
513 66632438676
514 68578763157
515 70580064290
516 72637843000
517 74753640436
518 76929039215
519 79165664222
520 81465182730
521 83829304948
522 86259785654
523 88758426250
524 91327076325
525 93967634616
526 96682049166
527 99472318020
528 102340491110
529 105288672416
530 108319021961
531 111433756794
532 114635151259
533 117925537932
534 121307309678
535 124782922108
536 128354895891
537 132025817792
538 135798341139
539 139675187014
540 143659146546
541 147753083619
542 151959937563
543 156282724264
544 160724536942
545 165288547662
546 169978009581
547 174796260344
548 179746724935
549 184832917040
550 190058440242
551 195426989444
552 200942353632
553 206608419836
554 212429176057
555 218408713152
556 224551226098
557 230861015756
558 237342492199
559 244000178994
560 250838716436
561 257862863930
562 265077501510
563 272487631940
564 280098384600
565 287915020032
566 295942933792
567 304187659330
568 312654869677
569 321350380056
570 330280152254
571 339450299624
572 348867091731
573 358536957508
574 368466487350
575 378662436236
576 389131728702
577 399881464420
578 410918923629
579 422251570594
580 433887056227
581 445833221922
582 458098105016
583 470689945180
584 483617190546
585 496888501620
586 510512754706
587 524499046336
588 538856699242
589 553595269808
590 568724554909
591 584254596529
592 600195685970
593 616558368774
594 633353451520
595 650592010642
596 668285399706
597 686445255088
598 705083500870
599 724212354388
600 743844334469
601 763992271008
602 784669313165
603 805888936268
604 827664947318
605 850011491716
606 872943062567
607 896474511250
608 920621057003
609 945398294876
610 970822202212
611 996909146404
612 1023675895603
613 1051139630438
614 1079317955216
615 1108228906990
616 1137890963036
617 1168323050100
618 1199544556444
619 1231575345084
620 1264435766743
621 1298146669952
622 1332729410051
623 1368205859996
624 1404598423896
625 1441930052064
626 1480224255708
627 1519505118482
628 1559797307264
629 1601126084682
630 1643517324096
631 1686997527046
632 1731593839744
633 1777334066460
634 1824246682318
635 1872360847296
636 1921706423464
637 1972313995084
638 2024214886847
639 2077441179638
640 2132025725231
641 2188002162362
642 2245404936779
643 2304269323704
644 2364631448323
645 2426528304362
646 2489997770891
647 2555078630976
648 2621810594667
649 2690234323858
650 2760391456051
651 2832324625696
652 2906077483477
653 2981694717982
654 3059222081681
655 3138706419040
656 3220195693823
657 3303739013372
658 3389386650945
659 3477190070640
660 3567201957072
661 3659476246979
662 3754068160609
663 3851034229202
664 3950432320831
665 4052321669480
666 4156762908296
667 4263818105656
668 4373550800782
669 4486026034932
670 4601310381835
671 4719471980780
672 4840580574135
673 4964707548622
674 5091925975460
675 5222310646356
676 5355938108624
677 5492886702784
678 5633236605266
679 5777069875672
680 5924470501770
681 6075524441016
682 6230319660901
683 6388946181738
684 6551496125881
685 6718063770820
686 6888745599976
687 7063640350832
688 7242849060856
689 7426475116768
690 7614624310550
691 7807404898986
692 8004927661882
693 8207305957056
694 8414655772889
695 8627095784776
696 8844747418743
697 9067734918632
698 9296185412727
699 9530228976222
700 9769998691415
701 10015630712464
702 10267264337522
703 10525042084808
704 10789109768477
705 11059616569492
706 11336715104769
707 11620561501442
708 11911315478454
709 12209140432736
710 12514203525419
711 12826675762300
712 13146732073575
713 13474551398586
714 13810316777660
715 14154215450548
716 14506438953694
717 14867183212228
718 15236648631494
719 15615040192844
720 16002567558356
721 16399445182624
722 16805892422431
723 17222133642094
724 17648398317632
725 18084921146002
726 18531942164394
727 18989706876460
728 19458466376273
729 19938477468858
730 20430002788920
731 20933310925248
732 21448676556443
733 21976380592876
734 22516710317808
735 23069959524806
736 23636428652610
737 24216424927238
738 24810262515606
739 25418262685936
740 26040753968422
741 26678072310934
742 27330561232896
743 27998571987032
744 28682463733490
745 29382603721234
746 30099367470401
747 30833138948828
748 31584310747440
749 32353284264698
750 33140469903342
751 33946287275772
752 34771165410673
753 35615542953100
754 36479868364948
755 37364600134360
756 38270206997880
757 39197168173562
758 40145973594450
759 41117124136034
760 42111131844653
761 43128520174526
762 44169824239578
763 45235591077842
764 46326379914630
765 47442762421458
766 48585322975374
767 49754658927730
768 50951380890352
769 52176113033590
770 53429493383892
771 54712174118302
772 56024821858565
773 57368117976528
774 58742758917997
775 60149456538856
776 61588938442312
777 63061948313028
778 64569246250748
779 66111609116672
780 67689830900041
781 69304723097292
782 70957115094485
783 72647854545478
784 74377807750221
785 76147860048034
786 77958916231726
787 79811900976065
788 81707759270569
789 83647456847044
790 85631980609196
791 87662339078450
792 89739562861780
793 91864705135701
794 94038842135434
795 96263073638696
796 98538523453383
797 100866339922544
798 103247696451945
799 105683792057696
800 108175851918398
801 110725127922832
802 113332899223245
803 116000472805578
804 118729184086126
805 121520397530522
806 124375507276087
807 127295937752500
808 130283144307712
809 133338613852962
810 136463865537794
811 139660451447742
812 142929957306656
813 146274003179530
814 149694244180409
815 153192371202118
816 156770111678780
817 160429230371712
818 164171530163155
819 167998852850972
820 171913079948891
821 175916133511824
822 180009976996359
823 184196616146744
824 188478099891580
825 192856521241176
826 197334018192223
827 201912774660776
828 206595021453152
829 211383037264590
830 216279149691660
831 221285736244680
832 226405225370619
833 231640097507706
834 236992886179484
835 242466179121192
836 248062619421267
837 253784906663856
838 259635798085715
839 265618109766296
840 271734717860665
841 277988559869796
842 284382635926970
843 290920010087550
844 297603811635702
845 304437236426492
846 311423548275830
847 318566080393004
848 325868236828823
849 333333493931566
850 340965401821733
851 348767585905238
852 356743748441638
853 364897670156296
854 373233211871316
855 381754316148944
856 390465008954289
857 399369401362552
858 408471691325775
859 417776165486614
860 427287201016583
861 437009267468612
862 446946928651853
863 457104844556244
864 467487773342213
865 478100573381642
866 488948205328943
867 500035734208000
868 511368331525152
869 522951277438600
870 534789962998062
871 546889892441336
872 559256685526425
873 571896079880936
874 584813933383746
875 598016226609352
876 611509065347504
877 625298683187178
878 639391444140827
879 653793845289076
880 668512519464935
881 683554238005768
882 698925913586609
883 714634603127944
884 730687510746685
885 747091990733612
886 763855550576493
887 780985854055734
888 798490724432050
889 816378147716744
890 834656275988618
891 853333430745378
892 872418106305676
893 891918973291878
894 911844882215754
895 932204867153306
896 953008149472601
897 974264141605232
898 995982450873200
899 1018172883406352
900 1040845448173789
901 1064010361110762
902 1087678049309961
903 1111859155262654
904 1136564541161592
905 1161805293306666
906 1187592726634244
907 1213938389352654
908 1240854067652766
909 1268351790474012
910 1296443834342214
911 1325142728321696
912 1354461259103418
913 1384412476210148
914 1415009697288300
915 1446266513461994
916 1478196794770522
917 1510814695734068
918 1544134661065942
919 1578171431516966
920 1612940049817442
921 1648455866690012
922 1684734546961025
923 1721792075811104
924 1759644765186503
925 1798309260360488
926 1837802546601880
927 1878141955927840
928 1919345173968230
929 1961430246982066
930 2004415589053784
931 2048319989456888
932 2093162620134917
933 2138963043283154
934 2185741219054862
935 2233517513436212
936 2282312706322710
937 2332147999777379
938 2383045026422096
939 2435025857947658
940 2488113013761633
941 2542329469825560
942 2597698667714270
943 2654244523874196
944 2711991439035767
945 2770964307760792
946 2831188528143979
947 2892690011726536
948 2955495193654423
949 3019631043056084
950 3085125073597727
951 3152005354188944
952 3220300519863474
953 3290039782897438
954 3361252944195484
955 3433970404921774
956 3508223178331542
957 3584042901771440
958 3661461848880516
959 3740512942054930
960 3821229765206600
961 3903646576794944
962 3987798323084466
963 4073720651593128
964 4161449924770186
965 4251023233965058
966 4342478413718212
967 4435854056360980
968 4531189526864807
969 4628524977909538
970 4727901365211395
971 4829360463169412
972 4932944880872754
973 5038698078450936
974 5146664383699997
975 5256889008962370
976 5369418068295415
977 5484298594995044
978 5601578559520861
979 5721306887798028
980 5843533479829681
981 5968309228600056
982 6095686039299319
983 6225716848944154
984 6358455646443198
985 6493957493076734
986 6632278543329937
987 6773476066054170
988 6917608465986865
989 7064735305714342
990 7214917328124987
991 7368216479321690
992 7524695931934990
993 7684420108802262
994 7847454707051061
995 8013866722676260
996 8183724475658010
997 8357097635590010
998 8534057247758700
999 8714675759631678
1000 8899027047803294