0 1
1 1
2 3
3 3
4 8
5 9
6 18
7 20
8 37
9 42
10 69
11 78
12 122
13 139
14 204
15 231
16 327
17 371
18 505
19 570
20 756
21 852
22 1100
23 1234
24 1563
25 1749
26 2173
27 2421
28 2964
29 3293
30 3974
31 4398
32 5247
33 5790
34 6831
35 7512
36 8782
37 9631
38 11160
39 12201
40 14033
41 15303
42 17475
43 19004
44 21568
45 23400
46 26400
47 28572
48 32069
49 34633
50 38679
51 41679
52 46344
53 49841
54 55186
55 59232
56 65337
57 70002
58 76937
59 82282
60 90138
61 96243
62 105100
63 112035
64 121995
65 129851
66 141005
67 149862
68 162324
69 172284
70 186156
71 197310
72 212719
73 225181
74 242241
75 256113
76 274964
77 290373
78 311142
79 328202
80 351043
81 369894
82 394947
83 415716
84 443150
85 465991
86 495960
87 521013
88 553701
89 581135
90 616711
91 646680
92 685344
93 718032
94 759968
95 795544
96 840969
97 879633
98 928747
99 970683
100 1023720
101 1069145
102 1126322
103 1175436
104 1237005
105 1290042
106 1356237
107 1413414
108 1484506
109 1546075
110 1622316
111 1688511
112 1770191
113 1841283
114 1928673
115 2004914
116 2098324
117 2180004
118 2279724
119 2367114
120 2473475
121 2566885
122 2680197
123 2779917
124 2900532
125 3006893
126 3135142
127 3248454
128 3384711
129 3505326
130 3649943
131 3778192
132 3931566
133 4067823
134 4230328
135 4374945
136 4547001
137 4700375
138 4882379
139 5044884
140 5237280
141 5409336
142 5612544
143 5794548
144 6009037
145 6201433
146 6427647
147 6630855
148 6869288
149 7083777
150 7334898
151 7561112
152 7825441
153 8063874
154 8341905
155 8593026
156 8885306
157 9149635
158 9456684
159 9734715
160 10057107
161 10349387
162 10687669
163 10994718
164 11349492
165 11671884
166 12043724
167 12382006
168 12771543
169 13126317
170 13534153
171 13905993
172 14332788
173 14722325
174 15168710
175 15576546
176 16043211
177 16470006
178 16957611
179 17403996
180 17913262
181 18379927
182 18911544
183 19399149
184 19953869
185 20463135
186 21041679
187 21573296
188 22176448
189 22731168
190 23359680
191 23938224
192 24592913
193 25196065
194 25877715
195 26506227
196 27215688
197 27870377
198 28608466
199 29290116
200 30057717
201 30767178
202 31565141
203 32303230
204 33132474
205 33900075
206 34761484
207 35559447
208 36453975
209 37283219
210 38211785
211 39073194
212 40036788
213 40931316
214 41930892
215 42859458
216 43896043
217 44859637
218 45934221
219 46933797
220 48047444
221 49084029
222 50237766
223 51312350
224 52507279
225 53620926
226 54858111
227 56011848
228 57292430
229 58487359
230 59812440
231 61049625
232 62420385
233 63700967
234 65118547
235 66443628
236 67909248
237 69280008
238 70794848
239 72212428
240 73777749
241 75243369
242 76860391
243 78375231
244 80045256
245 81610577
246 83334866
247 84951888
248 86731785
249 88401810
250 90238617
251 91962906
252 93858010
253 95637907
254 97592652
255 99429459
256 101445275
257 103340379
258 105418653
259 107373398
260 109515604
261 111531420
262 113738988
263 115817262
264 118091711
265 120233917
266 122576721
267 124784289
268 127197012
269 129471461
270 131955622
271 134298426
272 136855635
273 139268358
274 141900179
275 144384340
276 147092430
277 149649639
278 152435608
279 155067429
280 157932981
281 160641071
282 163587863
283 166373832
284 169403616
285 172269168
286 175383648
287 178330440
288 181531417
289 184561201
290 187850427
291 190964907
292 194344232
293 197545209
294 201016434
295 204305660
296 207870685
297 211250010
298 214910685
299 218381910
300 222140186
301 225705211
302 229562988
303 233223663
304 237182943
305 240941219
306 245003953
307 248861730
308 253029972
309 256989252
310 261265004
311 265327738
312 269713107
313 273881349
314 278378389
315 282654141
316 287265012
317 291650381
318 296377190
319 300874230
320 305719191
321 310330062
322 315295335
323 320022144
324 325109998
325 329954959
326 335167608
327 340132881
328 345472649
329 350560503
330 356029659
331 361242308
332 366843232
333 372183000
334 377918016
335 383387172
336 389258717
337 394859641
338 400870095
339 406605111
340 412756968
341 418628513
342 424924210
343 430934664
344 437376753
345 443528610
346 450119585
347 456415282
348 463157754
349 469599843
350 476496364
351 483087339
352 490140579
353 496883051
354 504095621
355 510992142
356 518366772
357 525420012
358 532959372
359 540171942
360 547878823
361 555253453
362 563130585
363 570669945
364 578720180
365 586427061
366 594653190
367 602530322
368 610935259
369 618985494
370 627572091
371 635798220
372 644569454
373 652974391
374 661933176
375 670519773
376 679669149
377 688440383
378 697783327
379 706742112
380 716281728
381 725431104
382 735170432
383 744513376
384 754455585
385 763995201
386 774143395
387 783882723
388 794240136
389 804182345
390 814752146
391 824900340
392 835685829
393 846043242
394 857047653
395 867617454
396 878844154
397 889629643
398 901081932
399 912086343
400 923767655
401 934994355
402 946908057
403 958360346
404 970509940
405 982191252
406 994580172
407 1006493874
408 1019125691
409 1031275285
410 1044153501
411 1056542421
412 1069670676
413 1082302493
414 1095684358
415 1108562574
416 1122201759
417 1135330014
418 1149230159
419 1162612024
420 1176776910
421 1190416095
422 1204849432
423 1218749577
424 1233455217
425 1247620103
426 1262601827
427 1277035164
428 1292296896
429 1307002536
430 1322548128
431 1337529852
432 1353363301
433 1368625033
434 1384750263
435 1400295855
436 1416716936
437 1432550385
438 1449271314
439 1465396544
440 1482421465
441 1498842546
442 1516175529
443 1532896458
444 1550541722
445 1567566643
446 1585528332
447 1602861315
448 1621143723
449 1638788987
450 1657396333
451 1675358022
452 1694294676
453 1712577084
454 1731847340
455 1750454686
456 1770062991
457 1788999645
458 1808950369
459 1828220625
460 1848518292
461 1868126597
462 1888775654
463 1908726378
464 1929731427
465 1950029094
466 1971394659
467 1992043716
468 2013774478
469 2034779527
470 2056880088
471 2078245653
472 2100720773
473 2122451535
474 2145305895
475 2167406456
476 2190644896
477 2213120016
478 2236747296
479 2259601656
480 2283622697
481 2306861137
482 2331280779
483 2354908059
484 2379731304
485 2403752345
486 2428984114
487 2453403756
488 2479049133
489 2503872378
490 2529936365
491 2555168134
492 2581655898
493 2607301275
494 2634217900
495 2660281887
496 2687632623
497 2714120387
498 2741910401
499 2768827026
500 2797061652
501 2824412388
502 2853096876
503 2880886890
504 2910026659
505 2938261285
506 2967861669
507 2996546157
508 3026612660
509 3055752429
510 3086290470
511 3115890854
512 3146906023
513 3176972526
514 3208470327
515 3239008368
516 3270994478
517 3302009647
518 3334489656
519 3365987457
520 3398967129
521 3430953239
522 3464438251
523 3496918260
524 3530914464
525 3563894136
526 3598407296
527 3631892308
528 3666928365
529 3700924569
530 3736489375
531 3771002535
532 3807102120
533 3842138177
534 3878778482
535 3914343288
536 3951530433
537 3987630018
538 4025370033
539 4062010338
540 4100309434
541 4137496579
542 4176360876
543 4214100891
544 4253536691
545 4291835787
546 4331849301
547 4370713598
548 4411311220
549 4450747020
550 4491935052
551 4531948566
552 4573733495
553 4614331117
554 4656719337
555 4697907369
556 4740905460
557 4782690389
558 4826304838
559 4868693058
560 4912930539
561 4955928630
562 5000795723
563 5044410172
564 5089913646
565 5134151127
566 5180297656
567 5225164749
568 5271961197
569 5317464671
570 5364917807
571 5411064336
572 5459181120
573 5505977568
574 5554764864
575 5602218000
576 5651682865
577 5699799649
578 5749949043
579 5798736339
580 5849577416
581 5899042281
582 5950582098
583 6000731492
584 6052977301
585 6103818378
586 6156777333
587 6208317150
588 6261996602
589 6314242411
590 6368649612
591 6421608567
592 6476750967
593 6530430419
594 6586315369
595 6640722570
596 6697357620
597 6752500020
598 6809892620
599 6865777570
600 6923935371
601 6980570421
602 7039500973
603 7096893573
604 7156604628
605 7214762429
606 7275261638
607 7334192190
608 7395487407
609 7455198462
610 7517297439
611 7577796648
612 7640707342
613 7702002559
614 7765732824
615 7827831801
616 7892389697
617 7955300391
618 8020693875
619 8084424140
620 8150661376
621 8215219272
622 8282308320
623 8347701804
624 8415650933
625 8481888169
626 8550705543
627 8617794591
628 8687488584
629 8755437713
630 8826016594
631 8894833968
632 8966306217
633 9036000210
634 9108374201
635 9178953082
636 9252237402
637 9323709651
638 9397912780
639 9470286771
640 9545417403
641 9618701723
642 9694768445
643 9768971574
644 9845983188
645 9921113820
646 9999079020
647 10075145742
648 10154073439
649 10231085053
650 10310984049
651 10388949249
652 10469828564
653 10548756261
654 10630624806
655 10710523802
656 10793390707
657 10874270022
658 10958144307
659 11040012852
660 11124903758
661 11207770663
662 11293687320
663 11377561605
664 11464513365
665 11549404271
666 11637400375
667 11723317032
668 11812366944
669 11899318704
670 11989431776
671 12077427880
672 12168613689
673 12257663601
674 12349931611
675 12440044683
676 12533404584
677 12624590393
678 12719051762
679 12811319772
680 12906892413
681 13000252314
682 13096945917
683 13191407286
684 13289231770
685 13384804411
686 13483769580
687 13580463183
688 13680579071
689 13778403555
690 13879680081
691 13978645250
692 14081092564
693 14181208452
694 14284836588
695 14386113114
696 14490932339
697 14593379653
698 14699400117
699 14803028253
700 14910260340
701 15015079565
702 15123533542
703 15229554006
704 15339240375
705 15446472462
706 15557401607
707 15665855584
708 15778038126
709 15887724495
710 16001170936
711 16112100081
712 16226821161
713 16339003703
714 16455010043
715 16568456484
716 16685758944
717 16800480024
718 16919089344
719 17035095684
720 17155022845
721 17272325305
722 17393581167
723 17512190487
724 17634786152
725 17754713313
726 17878659762
727 17999915624
728 18125224081
729 18247819746
730 18374501313
731 18498447762
732 18626513786
733 18751822243
734 18881283948
735 19007965515
736 19138834371
737 19266900395
738 19399187749
739 19528649454
740 19662366900
741 19793235756
742 19928394764
743 20060682118
744 20197294407
745 20331011853
746 20469089017
747 20604248025
748 20743801908
749 20880414197
750 21021456518
751 21159533682
752 21302076411
753 21441630294
754 21585685275
755 21726727596
756 21872306926
757 22014849655
758 22161965304
759 22306020285
760 22454684477
761 22600263807
762 22750488639
763 22897604288
764 23049402112
765 23198066304
766 23351449344
767 23501674176
768 23656654913
769 23808452737
770 23965043523
771 24118426563
772 24276640008
773 24431620745
774 24591469330
775 24748060116
776 24909556581
777 25067770026
778 25230926981
779 25390775566
780 25555605882
781 25717102347
782 25883618764
783 26046775719
784 26214991239
785 26379821555
786 26549749049
787 26716265466
788 26887918068
789 27056133588
790 27229524300
791 27399451794
792 27574593883
793 27746246485
794 27923153085
795 28096543797
796 28275228308
797 28450370397
798 28630846086
799 28807752686
800 28990033087
801 29168717598
802 29352816111
803 29533291800
804 29719222094
805 29901502495
806 30089278104
807 30273376617
808 30463011345
809 30648941639
810 30840449155
811 31028224764
812 31221619008
813 31411253736
814 31606548512
815 31798056028
816 31995265413
817 32188659657
818 32387797591
819 32583092367
820 32784173064
821 32981382449
822 33184419986
823 33383557920
824 33588566649
825 33789647346
826 33996641481
827 34199679018
828 34408673050
829 34613681779
830 34824690060
831 35031684195
832 35244721355
833 35453715387
834 35668795917
835 35879804198
836 36096942868
837 36309980028
838 36529191468
839 36744271998
840 36965571119
841 37182709789
842 37406111361
843 37625322801
844 37850841876
845 38072140997
846 38299792486
847 38523194058
848 38752993155
849 38978512230
850 39210473987
851 39438125476
852 39672265230
853 39902064327
854 40138397272
855 40370359029
856 40608900645
857 40843040399
858 41083806023
859 41320138968
860 41563144224
861 41801685840
862 42046946208
863 42287711832
864 42535243081
865 42778248337
866 43028066091
867 43273326459
868 43525446632
869 43772977881
870 44027416242
871 44277233996
872 44534006605
873 44786126778
874 45045249549
875 45299687910
876 45561177050
877 45817949659
878 46081821228
879 46340943999
880 46607214351
881 46868703491
882 47137388833
883 47401260402
884 47672377236
885 47938647588
886 48212212268
887 48480897610
888 48756926787
889 49028043621
890 49306553797
891 49580118477
892 49861126452
893 50137155629
894 50420678054
895 50699188230
896 50985242055
897 51266250030
898 51554852055
899 51838374480
900 52129541806
901 52415595631
902 52709345208
903 52997947233
904 53294296313
905 53585463639
906 53884429323
907 54178178900
908 54479778592
909 54776127672
910 55080378624
911 55379344308
912 55686264077
913 55987863769
914 56297469759
915 56601720711
916 56914030632
917 57220950401
918 57535981810
919 57845587800
920 58163358561
921 58475668482
922 58796196305
923 59111227714
924 59434530618
925 59752301379
926 60078397228
927 60398925051
928 60727832019
929 61051134923
930 61382871029
931 61708966878
932 62043550452
933 62372457420
934 62709906636
935 63041642742
936 63381976087
937 63716559661
938 64059795465
939 64397244681
940 64743401588
941 65083734933
942 65432831430
943 65776067234
944 66128122123
945 66474279030
946 66829310955
947 67178407452
948 67536435374
949 67888490263
950 68249532984
951 68604564909
952 68968641549
953 69326669471
954 69693798991
955 70054841712
956 70425043392
957 70789120032
958 71162412992
959 71529542512
960 71905946193
961 72276147873
962 72655681555
963 73028974515
964 73411657800
965 73788061481
966 74173913810
967 74553447492
968 74942488629
969 75325171914
970 75717421461
971 76103273790
972 76498751674
973 76887792811
974 77286518796
975 77678768343
976 78080762519
977 78476240403
978 78881522697
979 79280248682
980 79688839348
981 80090833524
982 80502752652
983 80908034946
984 81323302955
985 81731893621
986 82150530765
987 82562449893
988 82984476756
989 83399744765
990 83825181766
991 84243818910
992 84672686799
993 85094713662
994 85527033023
995 85952470024
996 86388261774
997 86817129663
998 87256414552
999 87688733913
1000 88131533025