0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 56
12 76
13 99
14 131
15 169
16 219
17 278
18 355
19 445
20 560
21 695
22 863
23 1060
24 1303
25 1586
26 1930
27 2331
28 2812
29 3370
30 4035
31 4802
32 5708
33 6751
34 7972
35 9373
36 11004
37 12866
38 15021
39 17475
40 20298
41 23501
42 27169
43 31316
44 36043
45 41373
46 47420
47 54218
48 61903
49 70515
50 80215
51 91058
52 103226
53 116792
54 131970
55 148847
56 167672
57 188556
58 211782
59 237489
60 266006
61 297495
62 332337
63 370733
64 413112
65 459718
66 511045
67 567377
68 629281
69 697097
70 771464
71 852785
72 941790
73 1038944
74 1145078
75 1260740
76 1386861
77 1524081
78 1673457
79 1835721
80 2012069
81 2203348
82 2410895
83 2635689
84 2879236
85 3142647
86 3427615
87 3735414
88 4067930
89 4426616
90 4813587
91 5230481
92 5679662
93 6162991
94 6683091
95 7242069
96 7842848
97 8487789
98 9180146
99 9922579
100 10718685
101 11571451
102 12484869
103 13462270
104 14508075
105 15626011
106 16820948
107 18097047
108 19459689
109 20913488
110 22464381
111 24117499
112 25879361
113 27755663
114 29753578
115 31879397
116 34141000
117 36545347
118 39101065
119 41815841
120 44699133
121 47759392
122 51006974
123 54451188
124 58103334
125 61973647
126 66074473
127 70417024
128 75014774
129 79880017
130 85027416
131 90470433
132 96225037
133 102305924
134 108730467
135 115514722
136 122677540
137 130236438
138 138211888
139 146622950
140 155491832
141 164839281
142 174689336
143 185064559
144 195990980
145 207493074
146 219599002
147 232335324
148 245732448
149 259819164
150 274628317
151 290191050
152 306542807
153 323717285
154 341752667
155 360685378
156 380556557
157 401405504
158 423276511
159 446211984
160 470259534
161 495464875
162 521879190
163 549551684
164 578537336
165 608889106
166 640665969
167 673924880
168 708729103
169 745139797
170 783224779
171 823049720
172 864687223
173 908207751
174 953689028
175 1001206560
176 1050843495
177 1102680731
178 1156807122
179 1213309282
180 1272282150
181 1333818347
182 1398019251
183 1464983897
184 1534820423
185 1607634648
186 1683541906
187 1762655144
188 1845097299
189 1930988902
190 2020460870
191 2113641746
192 2210670920
193 2311685347
194 2416833355
195 2526260833
196 2640125479
197 2758582603
198 2881799840
199 3009942381
200 3143188326
201 3281713335
202 3425706473
203 3575354434
204 3730857880
205 3892415064
206 4060238850
207 4234539718
208 4415543308
209 4603472960
210 4798567807
211 5001064654
212 5211216809
213 5429275296
214 5655508252
215 5890181641
216 6133579232
217 6385982615
218 6647691970
219 6919005360
220 7200240116
221 7491711584
222 7793755151
223 8106704235
224 8430913148
225 8766734325
226 9114541845
227 9474708078
228 9847627884
229 10233694450
230 10633324399
231 11046932797
232 11474958976
233 11917840913
234 12376041781
235 12850023467
236 13340274081
237 13847280602
238 14371557152
239 14913616956
240 15474001405
241 16053251090
242 16651935901
243 17270625121
244 17909918335
245 18570414804
246 19252745210
247 19957540052
248 20685462483
249 21437175703
250 22213376679
251 23014762750
252 23842066249
253 24696020064
254 25577393421
255 26486956385
256 27425516570
257 28393882812
258 29392902842
259 30423425839
260 31486341342
261 32582540670
262 33712956839
263 34878525088
264 36080223811
265 37319033910
266 38595981036
267 39912093745
268 41268446799
269 42666118368
270 44106234428
271 45589924702
272 47118368453
273 48692749154
274 50314301408
275 51984264609
276 53703931011
277 55474598072
278 57297617996
279 59174348721
280 61106204667
281 63094606641
282 65141033825
283 67246972275
284 69413968455
285 71643576320
286 73937412122
287 76297100350
288 78724329840
289 81220798227
290 83788269707
291 86428517974
292 89143385338
293 91934724449
294 94804458794
295 97754522858
296 100786924347
297 103903682767
298 107106893081
299 110398662992
300 113781178067
301 117256637363
302 120827320389
303 124495521052
304 128263616125
305 132133997837
306 136109143886
307 140191548291
308 144383793328
309 148688478610
310 153108294635
311 157645950412
312 162304248649
313 167086011548
314 171994158015
315 177031627599
316 182201459382
317 187506714404
318 192950556281
319 198536171691
320 204266853127
321 210145917422
322 216176790295
323 222362923263
324 228707879998
325 235215251220
326 241888743289
327 248732091045
328 255749148277
329 262943798861
330 270320049156
331 277881937002
332 285633626471
333 293579314708
334 301723328655
335 310070030110
336 318623914458
337 327389513504
338 336371496673
339 345574571567
340 355003587250
341 364663432919
342 374559143321
343 384695795077
344 395078614673
345 405712872418
346 416603992619
347 427757445564
348 439178859923
349 450873912271
350 462848442206
351 475108339372
352 487659660880
353 500508516254
354 513661187188
355 527124009925
356 540903497836
357 555006221205
358 569438932221
359 584208442570
360 599321750887
361 614785917651
362 630608195613
363 646795901962
364 663356551269
365 680297725375
366 697627208904
367 715352856341
368 733482730641
369 752024967452
370 770987916384
371 790380002821
372 810209871890
373 830486247337
374 851218078727
375 872414397347
376 894084466170
377 916237633254
378 938883484531
379 962031694125
380 985692180525
381 1009874953789
382 1034590274631
383 1059848498990
384 1085660240058
385 1112036209656
386 1138987383782
387 1166524840750
388 1194659929768
389 1223404106320
390 1252769103842
391 1282766765750
392 1313409220798
393 1344708711726
394 1376677773785
395 1409329060513
396 1442675525472
397 1476730244552
398 1511506601544
399 1547018106906
400 1583278586653
401 1620301998113
402 1658102622195
403 1696694875513
404 1736093506632
405 1776313404533
406 1817369798310
407 1859278062503
408 1902053920304
409 1945713245107
410 1990272267880
411 2035747374880
412 2082155318637
413 2129513012399
414 2177837744773
415 2227146970244
416 2277458528127
417 2328790429120
418 2381161078019
419 2434589056846
420 2489093351387
421 2544693130225
422 2601407975786
423 2659257659233
424 2718262375415
425 2778442514218
426 2839818899485
427 2902412556122
428 2966244953686
429 3031337769188
430 3097713134771
431 3165393396797
432 3234401367671
433 3304760080514
434 3376493045837
435 3449624001753
436 3524177174883
437 3600177026726
438 3677648518876
439 3756616854793
440 3837107750067
441 3919147169545
442 4002761602024
443 4087977793365
444 4174823025651
445 4263324845555
446 4353511348724
447 4445410903340
448 4539052439091
449 4634465166556
450 4731678870847
451 4830723626041
452 4931630094256
453 5034429235095
454 5139152609486
455 5245832084798
456 5354500143507
457 5465189583203
458 5577933830889
459 5692766637798
460 5809722398652
461 5928835841973
462 6050142354380
463 6173677665586
464 6299478178518
465 6427580648961
466 6558022520816
467 6690841601078
468 6826076400305
469 6963765802089
470 7103949409585
471 7246667209409
472 7391959923512
473 7539868668232
474 7690435311573
475 7843702126567
476 7999712154800
477 8158508854031
478 8320136467260
479 8484639665303
480 8652063921478
481 8822455148275
482 8995860078540
483 9172325896182
484 9351900623083
485 9534632744605
486 9720571602312
487 9909767013378
488 10102269670015
489 10298130752709
490 10497402335612
491 10700136994359
492 10906388217495
493 11116210007982
494 11329657301560
495 11546785561883
496 11767651205029
497 11992311189053
498 12220823444744
499 12453246458635
500 12689639710944
501 12930063251983
502 13174578146497
503 13423246044272
504 13676129630924
505 13933292191772
506 14194798070042
507 14460712223930
508 14731100691409
509 15006030141286
510 15285568344714
511 15569783719261
512 15858745808096
513 16152524817021
514 16451192100486
515 16754819692421
516 17063480799157
517 17377249323071
518 17696200363431
519 18020409732754
520 18349954464729
521 18684912324147
522 19025362321999
523 19371384217964
524 19723059043671
525 20080468597694
526 20443695976118
527 20812825060904
528 21187941057851
529 21569129977277
530 21956479180441
531 22350076852459
532 22750012556288
533 23156376698789
534 23569261092351
535 23988758413040
536 24414962770921
537 24847969160227
538 25287874037493
539 25734774764624
540 26188770194935
541 26649960108043
542 27118445804912
543 27594329534493
544 28077715096818
545 28568707262338
546 29067412383169
547 29573937804012
548 30088392482665
549 30610886392434
550 31141531150986
551 31680439415190
552 32227725518401
553 32783504856620
554 33347894535328
555 33921012746891
556 34502979425970
557 35093915619147
558 35693944149032
559 36303188974923
560 36921775866772
561 37549831756806
562 38187485422377
563 38834866829537
564 39492107824838
565 40159341469704
566 40836702742375
567 41524327862983
568 42222355004637
569 42930923610199
570 43650175112634
571 44380252242274
572 45121299757631
573 45873463743086
574 46636892349126
575 47411735081489
576 48198143550921
577 48996270752561
578 49806271826470
579 50628303327137
580 51462523993737
581 52309094010817
582 53168175788400
583 54039933212604
584 54924532436813
585 55822141122163
586 56732929238724
587 57657068296914
588 58594732158804
589 59546096259170
590 60511338428224
591 61490638102204
592 62484177156435
593 63492139106571
594 64514709952082
595 65552077366851
596 66604431554383
597 67671964427676
598 68754870475065
599 69853345930446
600 70967589649872
601 72097802270814
602 73244187100850
603 74406949265873
604 75586296609708
605 76782438832425
606 77995588401009
607 79225959676418
608 80473769836666
609 81739237992514
610 83022586121839
611 84324038175105
612 85643821021125
613 86982163540959
614 88339297586436
615 89715457062385
616 91110878896735
617 92525802112266
618 93960468808431
619 95415123221191
620 96890012717967
621 98385386845472
622 99901498336610
623 101438602147507
624 102996956476443
625 104576821788678
626 106178461848862
627 107802142733545
628 109448133875851
629 111116707066880
630 112808137512794
631 114522702823644
632 116260684084322
633 118022364830734
634 119808032133361
635 121617975562028
636 123452488282190
637 125311866006827
638 127196408106966
639 129106416550561
640 131042197025994
641 133004057869217
642 134992311200371
643 137007271837688
644 139049258448704
645 141118592450838
646 143215599175928
647 145340606758766
648 147493947315091
649 149675955816530
650 151886971283614
651 154127335647007
652 156397394954227
653 158697498218501
654 161027998639309
655 163389252437306
656 165781620090248
657 168205465153882
658 170661155511948
659 173149062184337
660 175669560591308
661 178223029347335
662 180809851541148
663 183430413515160
664 186085106159940
665 188774323680606
666 191498464905879
667 194257932039815
668 197053131987068
669 199884475089830
670 202752376467952
671 205657254742465
672 208599533390689
673 211579639454716
674 214598004913143
675 217655065374404
676 220751261463716
677 223887037502680
678 227062842911608
679 230279130873681
680 233536359754342
681 236834991749904
682 240175494322597
683 243558338835061
684 246984002001153
685 250452964504650
686 253965712467537
687 257522736052789
688 261124530948696
689 264771596957163
690 268464439494245
691 272203568162225
692 275989498268087
693 279822749379276
694 283703846858618
695 287633320405248
696 291611705606117
697 295639542460338
698 299717376949076
699 303845759543149
700 308025246789806
701 312256399805100
702 316539785877720
703 320875976944351
704 325265551212317
705 329709091617828
706 334207187465925
707 338760432873134
708 343369428424869
709 348034779600661
710 352757098450873
711 357537002004362
712 362375113962950
713 367272063093102
714 372228484938292
715 377245020192854
716 382322316434089
717 387461026478171
718 392661810130450
719 397925332524952
720 403252265893044
721 408643287884662
722 414099083357237
723 419620342678524
724 425207763534149
725 430862049213673
726 436583910436936
727 442374063621437
728 448233232729397
729 454162147516302
730 460161545397089
731 466232169677475
732 472374771439419
733 478590107753327
734 484878943584721
735 491242049987186
736 497680206028587
737 504194196966429
738 510784816193817
739 517452863395220
740 524199146514157
741 531024479889237
742 537929686241911
743 544915594794476
744 551983043278021
745 559132876030425
746 566365946026519
747 573683112955926
748 581085245273742
749 588573218259911
750 596147916090627
751 603810229877202
752 611561059760219
753 619401312927778
754 627331905730655
755 635353761681668
756 643467813592006
757 651675001549666
758 659976275079055
759 668372591098309
760 676864916100418
761 685454224091205
762 694141498792166
763 702927731557020
764 711813923598325
765 720801083882481
766 729890231378355
767 739082392932516
768 748378605540055
769 757779914197909
770 767287374200042
771 776902048968695
772 786625012372111
773 796457346535559
774 806400144181766
775 816454506419564
776 826621545109188
777 836902380628405
778 847298144260873
779 857809975941556
780 868439026668334
781 879186456224528
782 890053435615977
783 901041144770523
784 912150774998649
785 923383526671826
786 934740611706917
787 946223251221153
788 957832678042540
789 969570134341289
790 981436874164368
791 993434161045274
792 1005563270562911
793 1017825487927480
794 1030222110565932
795 1042754445683821
796 1055423812875402
797 1068231541663392
798 1081178974133938
799 1094267462451953
800 1107498371523261
801 1120873076485359
802 1134392965394808
803 1148059436695385
804 1161873901930871
805 1175837783188304
806 1189952515838513
807 1204219545954294
808 1218640333076724
809 1233216347610226
810 1247949073614894
811 1262840006176082
812 1277890654225096
813 1293102537883171
814 1308477191308510
815 1324016160016668
816 1339721003754130
817 1355593293792729
818 1371634615832195
819 1387846567268394
820 1404230760122822
821 1420788818286723
822 1437522380477750
823 1454433097457544
824 1471522635017953
825 1488792671171932
826 1506244899167276
827 1523881024652902
828 1541702768720310
829 1559711865042771
830 1577910062947020
831 1596299124525163
832 1614880827734503
833 1633656963484300
834 1652629338763921
835 1671799773701970
836 1691170104725255
837 1710742181590125
838 1730517870570171
839 1750499051461855
840 1770687620801164
841 1791085488841021
842 1811694582799449
843 1832516843808590
844 1853554230192185
845 1874808714388395
846 1896282286256831
847 1917976949972604
848 1939894727365486
849 1962037654784989
850 1984407786469514
851 2007007191384636
852 2029837956622451
853 2052902184210506
854 2076201994543934
855 2099739523164850
856 2123516924225058
857 2147536367238149
858 2171800040573036
859 2196310148176077
860 2221068913098091
861 2246078574186334
862 2271341389642776
863 2296859633688188
864 2322635600151859
865 2348671599105160
866 2374969960485401
867 2401533030698671
868 2428363176275574
869 2455462780445607
870 2482834246825039
871 2510479995960113
872 2538402469049775
873 2566604124457541
874 2595087441466761
875 2623854916763470
876 2652909068224406
877 2682252431368124
878 2711887563178558
879 2741817038524154
880 2772043454014657
881 2802569424390621
882 2833397586413674
883 2864530595223637
884 2895971128265009
885 2927721881611534
886 2959785573926565
887 2992164942757440
888 3024862748529971
889 3057881770809798
890 3091224812333866
891 3124894695238546
892 3158894265125699
893 3193226387260005
894 3227893950669836
895 3262899864310950
896 3298247061205029
897 3333938494569551
898 3369977141991609
899 3406366001526350
900 3443108095906325
901 3480206468605627
902 3517664188087694
903 3555484343834946
904 3593670050632541
905 3632224444566016
906 3671150687341260
907 3710451962247226
908 3750131478515068
909 3790192467245696
910 3830638185805631
911 3871471913721890
912 3912696957114800
913 3954316644557289
914 3996334331547616
915 4038753396332866
916 4081577244419070
917 4124809304361452
918 4168453032312231
919 4212511907774573
920 4256989438191099
921 4301889154661345
922 4347214616568448
923 4392969407262687
924 4439157138726553
925 4485781447221372
926 4532845997993834
927 4580354480885469
928 4628310615078062
929 4676718144668561
930 4725580843453676
931 4774902510467132
932 4824686974806534
933 4874938091132784
934 4925659744536581
935 4976855846002638
936 5028530337316070
937 5080687186488317
938 5133330392706590
939 5186463981721227
940 5240092010835562
941 5294218564257395
942 5348847758129569
943 5403983735842411
944 5459630673108138
945 5515792773234082
946 5572474272238267
947 5629679434086103
948 5687412555847412
949 5745677962893380
950 5804480014098281
951 5863823096996448
952 5923711633025975
953 5984150072648473
954 6045142900635004
955 6106694631145401
956 6168809813059672
957 6231493025016673
958 6294748880788278
959 6358582024280117
960 6422997134948797
961 6487998922761454
962 6553592133659336
963 6619781544475944
964 6686571968444148
965 6753968250075754
966 6821975270712453
967 6890597943363492
968 6959841218303796
969 7029710077869486
970 7100209542100404
971 7171344663496297
972 7243120532704016
973 7315542273231058
974 7388615047180789
975 7462344049923113
976 7536734515874865
977 7611791713130490
978 7687520949287933
979 7763927566035889
980 7841016945028608
981 7918794502429494
982 7997265694831969
983 8076436013762327
984 8156310991646896
985 8236896196270758
986 8318197236794681
987 8400219758169449
988 8482969447199660
989 8566452026916580
990 8650673262689142
991 8735638956551840
992 8821354953366413
993 8907827135104572
994 8995061427057400
995 9083063792075891
996 9171840236828352
997 9261396805995263
998 9351739588578256
999 9442874712048993
1000 9534808348706751