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 77
13 100
14 133
15 172
16 224
17 285
18 366
19 460
20 582
21 725
22 905
23 1116
24 1380
25 1686
26 2063
27 2503
28 3036
29 3655
30 4401
31 5262
32 6290
33 7476
34 8877
35 10489
36 12384
37 14552
38 17084
39 19978
40 23334
41 27156
42 31570
43 36578
44 42333
45 48849
46 56297
47 64707
48 74287
49 85067
50 97299
51 111036
52 126560
53 143948
54 163540
55 185425
56 210005
57 237405
58 268079
59 302196
60 340293
61 382562
62 429636
63 481769
64 539672
65 603666
66 674585
67 752802
68 839286
69 934502
70 1039543
71 1154981
72 1282083
73 1421506
74 1574714
75 1742509
76 1926533
77 2127747
78 2348042
79 2588523
80 2851355
81 3137850
82 3450438
83 3790670
84 4161319
85 4564153
86 5002329
87 5477923
88 5994463
89 6554363
90 7161629
91 7819004
92 8531017
93 9300841
94 10133529
95 11032739
96 12004167
97 13051942
98 14182475
99 15400502
100 16713148
101 18125814
102 19646498
103 21281274
104 23039092
105 24926852
106 26954477
107 29129786
108 31463856
109 33965430
110 36646856
111 39518001
112 42592509
113 45881477
114 49400076
115 53160671
116 57180092
117 61472199
118 66055542
119 70945627
120 76162989
121 81724822
122 87653830
123 93969189
124 100695843
125 107855124
126 115474549
127 123577695
128 132194866
129 141352216
130 151082958
131 161416060
132 172388026
133 184030746
134 196384297
135 209483911
136 223373383
137 238091562
138 253686437
139 270200645
140 287686698
141 306191497
142 325772294
143 346480619
144 368379006
145 391523820
146 415983299
147 441819235
148 469105831
149 497910726
150 528314754
151 560391695
152 594229505
153 629908782
154 667524961
155 707165997
156 748935563
157 792929324
158 839259810
159 888031219
160 939365365
161 993375601
162 1050193944
163 1109943379
164 1172766841
165 1238797888
166 1308190930
167 1381090877
168 1457664666
169 1538069121
170 1622484589
171 1711080939
172 1804052588
173 1901583352
174 2003882972
175 2111149939
176 2223610336
177 2341478619
178 2464998052
179 2594400159
180 2729946816
181 2871887468
182 3020503840
183 3176064836
184 3338873011
185 3509218000
186 3687424878
187 3873805083
188 4068707635
189 4272467521
190 4485458922
191 4708041905
192 4940617736
193 5183572815
194 5437337195
195 5702325669
196 5978998490
197 6267800603
198 6569224718
199 6883747464
200 7211895961
201 7554180856
202 7911165395
203 8283396339
204 8671475616
205 9075987879
206 9497576045
207 9936865387
208 10394541798
209 10871273563
210 11367792525
211 11884812118
212 12423112770
213 12983456152
214 13566673647
215 14173577980
216 14805054848
217 15461970494
218 16145268015
219 16855870747
220 17594781914
221 18362985147
222 19161547676
223 19991516353
224 20854025918
225 21750190477
226 22681215492
227 23648286058
228 24652682732
229 25695664944
230 26778592414
231 27902803544
232 29069740890
233 30280826060
234 31537589457
235 32841539820
236 34194299999
237 35597471079
238 37052772644
239 38561903014
240 40126684137
241 41748916034
242 43430528315
243 45173428665
244 46979659225
245 48851240864
246 50790334667
247 52799079872
248 54879762482
249 57034646782
250 59266149323
251 61576665764
252 63968750386
253 66444936098
254 69007921736
255 71660385050
256 74405175795
257 77245123676
258 80183237509
259 83222505711
260 86366103824
261 89617187452
262 92979106162
263 96455190852
264 100048974197
265 103763970008
266 107603902772
267 111572478795
268 115673622594
269 119911242044
270 124289471937
271 128812430413
272 133484472277
273 138309936606
274 143293407570
275 148439455461
276 153752905208
277 159238568080
278 164901520768
279 170746827516
280 176779827261
281 183005848685
282 189430505762
283 196059402688
284 202898440732
285 209953512926
286 217230819692
287 224736555811
288 232477235048
289 240459366307
290 248689790475
291 257175345490
292 265923212599
293 274940573134
294 284234964556
295 293813925546
296 303685365079
297 313857195693
298 324337712773
299 335135218803
300 346258413115
301 357716003670
302 369517110864
303 381670866542
304 394186828724
305 407074570971
306 420344108442
307 434005473837
308 448069158407
309 462545674303
310 477446007408
311 492781169215
312 508562661764
313 524802015218
314 541511268879
315 558702494141
316 576388288106
317 594581285375
318 613294664723
319 632541645528
320 652336011534
321 672691591725
322 693622797703
323 715144092478
324 737270541762
325 760017266438
326 783400012168
327 807434585186
328 832137436383
329 857525084236
330 883614713879
331 910423582530
332 937969638005
333 966270906433
334 995346126358
335 1025214122588
336 1055894456220
337 1087406779942
338 1119771508841
339 1153009156753
340 1187141023633
341 1222188517155
342 1258173857200
343 1295119377607
344 1333048252678
345 1371983778851
346 1411950118977
347 1452971568152
348 1495073316143
349 1538280692213
350 1582619951047
351 1628117496125
352 1674800684513
353 1722697033409
354 1771835044388
355 1822243387532
356 1873951750514
357 1926990000056
358 1981389051198
359 2037180010722
360 2094395067030
361 2153066609864
362 2213228146660
363 2274913398087
364 2338157235782
365 2402994758784
366 2469462253292
367 2537596243873
368 2607434481155
369 2679014967508
370 2752376967582
371 2827560013543
372 2904604938920
373 2983552857201
374 3064446225387
375 3147327795434
376 3232241701952
377 3319232392038
378 3408345737823
379 3499627937998
380 3593126661680
381 3688889921297
382 3786967242213
383 3887408512533
384 3990265178978
385 4095589066857
386 4203433609169
387 4313852636184
388 4426901631720
389 4542636498358
390 4661114841665
391 4782394703748
392 4906535882478
393 5033598633023
394 5163645015998
395 5296737573046
396 5432940704450
397 5572319311409
398 5714940210713
399 5860870743090
400 6010180218373
401 6162938496471
402 6319217463860
403 6479089579261
404 6642629389110
405 6809912037556
406 6981014814308
407 7156015635549
408 7334994624754
409 7518032556516
410 7705212478593
411 7896618117970
412 8092335537010
413 8292451508870
414 8497055208633
415 8706236549505
416 8920087917237
417 9138702466676
418 9362175892327
419 9590604692395
420 9824087976141
421 10062725686741
422 10306620454379
423 10555875777203
424 10810597912425
425 11070894023088
426 11336874108118
427 11608649105627
428 11886332870923
429 12170040235864
430 12459889027098
431 12755998089192
432 13058489343812
433 13367485767255
434 13683113500216
435 14005499778956
436 14334775087308
437 14671071049814
438 15014522626994
439 15365265960420
440 15723440620990
441 16089187405409
442 16462650629122
443 16843975882557
444 17233312369463
445 17630810612810
446 18036624848940
447 18450910682296
448 18873827526399
449 19305536216370
450 19746201497841
451 20195989586461
452 20655070715246
453 21123616640504
454 21601803238608
455 22089807967355
456 22587812512970
457 23096000196013
458 23614558679829
459 24143677320094
460 24683549925051
461 25234372058343
462 25796343852221
463 26369667252047
464 26954548893764
465 27551197289465
466 28159825759424
467 28780649568433
468 29413888913275
469 30059765998102
470 30718508089414
471 31390344529503
472 32075509848563
473 32774240726575
474 33486779163794
475 34213369378614
476 34954261048564
477 35709706143496
478 36479962226684
479 37265289233736
480 38065952834753
481 38882221146377
482 39714368167954
483 40562670425685
484 41427410471646
485 42308873471180
486 43207350766106
487 44123136391992
488 45056530718579
489 46007836896205
490 46977364562296
491 47965426228095
492 48972341052248
493 49998431154359
494 51044025469514
495 52109455987568
496 53195061676675
497 54301184660233
498 55428174210850
499 56576382850627
500 57746170429523
501 58937900148188
502 60151942708793
503 61388672272367
504 62648470683172
505 63931723346131
506 65238823539556
507 66570168211498
508 67926162368084
509 69307214801519
510 70713742555564
511 72146166569888
512 73604916237619
513 75090424965209
514 76603134809279
515 78143491964788
516 79711951482329
517 81308972669202
518 82935023902987
519 84590577944252
520 86276116832813
521 87992127125666
522 89739104877563
523 91517550787852
524 93327975281290
525 95170893562903
526 97046830785397
527 98956317025692
528 100899892540180
529 102878102646479
530 104891503083428
531 106940654796711
532 109026129389101
533 111148503824455
534 113308365969914
535 115506309200892
536 117742938052211
537 120018862723130
538 122334704822890
539 124691091790316
540 127088662735115
541 129528062754522
542 132009948888340
543 134534984331204
544 137103844485919
545 139717211086793
546 142375778353083
547 145080247004904
548 147831330534876
549 150629749115564
550 153476235973876
551 156371531205506
552 159316388253516
553 162311567611142
554 165357843423668
555 168455997078095
556 171606823911889
557 174811126705940
558 178069722502115
559 181383435979827
560 184753106401648
561 188179580872370
562 191663721396253
563 195206398035043
564 198808496078354
565 202470909080846
566 206194546166043
567 209980324941078
568 213829178916526
569 217742050316139
570 221719897614749
571 225763688222101
572 229874406159279
573 234053044615456
574 238300613745379
575 242618133116532
576 247006639629275
577 251467179833407
578 256000817992513
579 260608628268215
580 265291702910263
581 270051144326956
582 274888073403149
583 279803621434705
584 284798938596092
585 289875185737619
586 295033542984103
587 300275201413446
588 305601371788079
589 311013276092577
590 316512156420737
591 322099266370419
592 327775880066698
593 333543283433527
594 339402783355231
595 345355698801556
596 351403370150475
597 357547150165295
598 363788413459168
599 370128547343892
600 376568961437951
601 383111078363391
602 389756343521587
603 396506215636292
604 403362176676406
605 410325722265952
606 417398371756240
607 424581658477974
608 431877139987141
609 439286388157809
610 446810999581007
611 454452585518997
612 462212782459076
613 470093241904350
614 478095641108023
615 486221672698677
616 494473055573141
617 502851524378218
618 511358840564671
619 519996781699165
620 528767152705108
621 537671775003281
622 546712497917617
623 555891187666504
624 565209738935519
625 574670063693028
626 584274102956885
627 594023815432222
628 603921189448992
629 613968231445098
630 624166978077465
631 634519484522809
632 645027836789430
633 655694139834015
634 666520530050978
635 677509163228532
636 688662227217709
637 699981929699855
638 711470511063851
639 723130231982783
640 734963386474986
641 746972289314315
642 759159289277836
643 771526756360497
644 784077095238134
645 796812732284853
646 809736129226906
647 822849769987298
648 836156174532800
649 849657885516385
650 863357482347465
651 877257567629790
652 891360781429213
653 905669787532816
654 920187287917145
655 934916008797803
656 949858715328382
657 965018197438735
658 980397284738854
659 995998832171635
660 1011825735124108
661 1027880914863720
662 1044167333888613
663 1060687981144950
664 1077445887589153
665 1094444111213422
666 1111685752823024
667 1129173940837618
668 1146911847315450
669 1164902672528565
670 1183149661206806
671 1201656086914100
672 1220425268514797
673 1239460554318436
674 1258765338801756
675 1278343046519354
676 1298197149052869
677 1318331148716102
678 1338748595734632
679 1359453071711299
680 1380448207069792
681 1401737664278469
682 1423325155529403
683 1445214425749161
684 1467409270515950
685 1489913518823086
686 1512731051269293
687 1535865782572143
688 1559321680001565
689 1583102745673265
690 1607213035228877
691 1631656639873524
692 1656437705337879
693 1681560413657745
694 1707029002388021
695 1732847746154409
696 1759020976122067
697 1785553061283424
698 1812448428218369
699 1839711542115292
700 1867346926791371
701 1895359145478365
702 1923752821106597
703 1952532616817875
704 1981703256550196
705 2011269505275573
706 2041236189853946
707 2071608179027543
708 2102390404546936
709 2133587840884085
710 2165205526669242
711 2197248544119654
712 2229722040754321
713 2262631208571467
714 2295981306044889
715 2329777637010729
716 2364025572984285
717 2398730531753744
718 2433897999984396
719 2469533511552495
720 2505642670439980
721 2542231128768747
722 2579304610026479
723 2616868886798178
724 2654929804288470
725 2693493257785140
726 2732565216481825
727 2772151700632166
728 2812258805713682
729 2852892679270046
730 2894059545381485
731 2935765681229970
732 2978017441879399
733 3020821236522074
734 3064183553611200
735 3108110936785364
736 3152610010317057
737 3197687454751569
738 3243350032675642
739 3289604564027386
740 3336457952227839
741 3383917159159283
742 3431989231623396
743 3480681276024446
744 3530000485157420
745 3579954112552499
746 3630549499637719
747 3681794049741290
748 3733695255590799
749 3786260673011480
750 3839497948766269
751 3893414793904588
752 3948019011988058
753 4003318472087061
754 4059321137354051
755 4116035037706114
756 4173468298749426
757 4231629114102165
758 4290525774716774
759 4350166640839599
760 4410560171691217
761 4471714897102685
762 4533639447558435
763 4596342525461608
764 4659832935586383
765 4724119555969542
766 4789211368732406
767 4855117430638630
768 4921846904289481
769 4989409028300074
770 5057813148916816
771 5127068689808294
772 5197185184063328
773 5268172243638244
774 5340039591740201
775 5412797031881172
776 5486454480695571
777 5561021936597947
778 5636509512993279
779 5712927406580186
780 5790285930957815
781 5868595484524602
782 5947866584532793
783 6028109834578817
784 6109335959061977
785 6191555770310070
786 6274780203447118
787 6359020283102325
788 6444287158738111
789 6530592070939236
790 6617946387157647
791 6706361567625460
792 6795849201520726
793 6886420972452082
794 6978088695098725
795 7070864280262638
796 7164759771937379
797 7259787311973462
798 7355959177581056
799 7453287745554278
800 7551785530261372
801 7651465147424595
802 7752339352552455
803 7854421004320845
804 7957723103451597
805 8062258755640386
806 8168041210937238
807 8275083826216932
808 8383400105014103
809 8493003659583688
810 8603908251195950
811 8716127751730360
812 8829676184486468
813 8944567685307766
814 9060816543860965
815 9178437164337513
816 9297444107205727
817 9417852049433115
818 9539675826769433
819 9662930393485326
820 9787630865136925
821 9913792477870411
822 10041430631673700
823 10170560849187904
824 10301198819504421
825 10433360356479698
826 10567061443028241
827 10702318188990415
828 10839146875926037
829 10977563914475886
830 11117585889716453
831 11259229518010489
832 11402511692871428
833 11547449441354711
834 11694059970437621
835 11842360622889874
836 11992368924229676
837 12144102538069823
838 12297579313598412
839 12452817240452270
840 12609834496727201
841 12768649403316907
842 12929280472515902
843 13091746361819079
844 13256065923063613
845 13422258155743106
846 13590342256694452
847 13760337572862478
848 13932263651595162
849 14106140192854812
850 14281987100067926
851 14459824431836906
852 14639672453349652
853 14821551587527413
854 15005482467059836
855 15191485884983929
856 15379582847288671
857 15569794522981255
858 15762142297267488
859 15956647721038555
860 16153332564693253
861 16352218767041146
862 16553328489710702
863 16756684065525094
864 16962308053501511
865 17170223186632573
866 17380452427545237
867 17593018915682600
868 17807946023564245
869 18025257303426862
870 18244976544092527
871 18467127716998668
872 18691735033743028
873 18918822891498687
874 19148415931177463
875 19380538982288564
876 19615217121725917
877 19852475618000697
878 20092339990723795
879 20334835954206754
880 20579989477578902
881 20827826727817483
882 21078374130506201
883 21331658312222305
884 21587706162008037
885 21846544773110221
886 22108201505104028
887 22372703925046004
888 22640079870255888
889 22910357388810495
890 23183564803057661
891 23459730649445300
892 23738883742704601
893 24021053115077488
894 24306268081176037
895 24594558176533255
896 24885953223213066
897 25180483267679772
898 25478178647095637
899 25779069926572354
900 26083187966162213
901 26390563857416122
902 26701228991145355
903 27015214993280246
904 27332553793337142
905 27653277559643504
906 27977418768517297
907 28305010138780481
908 28636084701728134
909 28970675734925468
910 29308816832901268
911 29650541840294244
912 29995884923277013
913 30344880501973411
914 30697563322692971
915 31053968389613112
916 31414131037756212
917 31778086864004956
918 32145871800829528
919 32517522046555054
920 32893074139919233
921 33272564889586813
922 33656031449469716
923 34043511247556931
924 34435042062003566
925 34830661949194783
926 35230409320686805
927 35634322870498581
928 36042441652834274
929 36454805008673517
930 36871452644283204
931 37292424557022186
932 37717761114725767
933 38147502980719597
934 38581691194006297
935 39020367093559569
936 39463572399319636
937 39911349135683100
938 40363739713393395
939 40820786852219808
940 41282533663669836
941 41749023572930912
942 42220300402412773
943 42696408292864597
944 43177391787833905
945 43663295753953679
946 44154165466244564
947 44650046527645672
948 45150984955167048
949 45657027098576480
950 46168219727491676
951 46684609949216256
952 47206245296695811
953 47733173645579385
954 48265443303047777
955 48803102924009998
956 49346201600893577
957 49894788778970352
958 50448914347032842
959 51008628551925789
960 51573982090115845
961 52145026021337934
962 52721811861151012
963 53304391493692200
964 53892817265139959
965 54487141895655139
966 55087418573760230
967 55693700867373490
968 56306042819197373
969 56924498856839838
970 57549123889133246
971 58179973215422086
972 58817102622819861
973 59460568294568992
974 60110426908331801
975 60766735543615313
976 61429551781014824
977 62098933608785629
978 62774939523048163
979 63457628433409379
980 64147059764225981
981 64843293359269332
982 65546389583965215
983 66256409229184413
984 66973413614466757
985 67697464490839750
986 68428624145126482
987 69166955301784762
988 69912521228214484
989 70665385635702209
990 71425612785737305
991 72193267389961219
992 72968414717592394
993 73751120494373904
994 74541451011022615
995 75339473021260304
996 76145253851295109
997 76958861296835013
998 77780363733704738
999 78609830013833755
1000 79447329576921235