0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 3
10 3
11 4
12 4
13 5
14 5
15 6
16 6
17 8
18 8
19 9
20 10
21 12
22 12
23 14
24 15
25 17
26 18
27 20
28 21
29 25
30 26
31 29
32 31
33 35
34 36
35 41
36 43
37 48
38 51
39 56
40 59
41 66
42 70
43 76
44 81
45 89
46 94
47 103
48 109
49 119
50 126
51 137
52 144
53 158
54 167
55 180
56 191
57 207
58 218
59 236
60 250
61 269
62 285
63 306
64 323
65 349
66 368
67 394
68 417
69 447
70 471
71 505
72 533
73 570
74 602
75 642
76 677
77 724
78 763
79 812
80 857
81 913
82 961
83 1023
84 1078
85 1145
86 1207
87 1281
88 1348
89 1432
90 1507
91 1596
92 1681
93 1781
94 1872
95 1983
96 2085
97 2205
98 2319
99 2451
100 2575
101 2723
102 2860
103 3018
104 3171
105 3347
106 3512
107 3705
108 3889
109 4099
110 4302
111 4531
112 4752
113 5006
114 5249
115 5522
116 5791
117 6092
118 6383
119 6713
120 7033
121 7391
122 7743
123 8133
124 8515
125 8944
126 9363
127 9825
128 10285
129 10791
130 11289
131 11841
132 12386
133 12984
134 13580
135 14230
136 14876
137 15588
138 16292
139 17058
140 17828
141 18664
142 19496
143 20405
144 21312
145 22295
146 23282
147 24348
148 25416
149 26577
150 27738
151 28988
152 30251
153 31609
154 32973
155 34445
156 35926
157 37515
158 39122
159 40841
160 42576
161 44441
162 46320
163 48328
164 50366
165 52539
166 54736
167 57085
168 59463
169 61995
170 64567
171 67300
172 70073
173 73028
174 76023
175 79201
176 82438
177 85869
178 89353
179 93053
180 96814
181 100795
182 104853
183 109140
184 113506
185 118130
186 122835
187 127800
188 132872
189 138220
190 143670
191 149425
192 155294
193 161476
194 167792
195 174437
196 181222
197 188371
198 195667
199 203334
200 211181
201 219420
202 227839
203 236688
204 245734
205 255224
206 264940
207 275123
208 285542
209 296474
210 307655
211 319364
212 331364
213 343923
214 356779
215 370242
216 384028
217 398445
218 413224
219 428667
220 444491
221 461039
222 477990
223 495689
224 513848
225 532799
226 552224
227 572506
228 593300
229 614987
230 637240
231 660434
232 684224
233 709035
234 734478
235 760981
236 788191
237 816521
238 845588
239 875861
240 906926
241 939251
242 972443
243 1006963
244 1042399
245 1079268
246 1117107
247 1156441
248 1196844
249 1238828
250 1281930
251 1326728
252 1372725
253 1420497
254 1469571
255 1520517
256 1572839
257 1627172
258 1682964
259 1740858
260 1800345
261 1862054
262 1925435
263 1991193
264 2058735
265 2128770
266 2200733
267 2275325
268 2351955
269 2431399
270 2513004
271 2597556
272 2684448
273 2774456
274 2866924
275 2962715
276 3061129
277 3163031
278 3267751
279 3376151
280 3487531
281 3602838
282 3721302
283 3843884
284 3969868
285 4100202
286 4234116
287 4372661
288 4515013
289 4662231
290 4813525
291 4969951
292 5130685
293 5296882
294 5467642
295 5644136
296 5825523
297 6012965
298 6205561
299 6404589
300 6609088
301 6820350
302 7037451
303 7261683
304 7492084
305 7730061
306 7974565
307 8227027
308 8486465
309 8754299
310 9029484
311 9313573
312 9605455
313 9906700
314 10216240
315 10535652
316 10863822
317 11202461
318 11550360
319 11909260
320 12278025
321 12658393
322 13049156
323 13452206
324 13866262
325 14293239
326 14731907
327 15184189
328 15648810
329 16127848
330 16619919
331 17127143
332 17648220
333 18185269
334 18736912
335 19305447
336 19889414
337 20491145
338 21109237
339 21746041
340 22400102
341 23073947
342 23766009
343 24478867
344 25211044
345 25965130
346 26739565
347 27537142
348 28356213
349 29199616
350 30065773
351 30957548
352 31873306
353 32816120
354 33784230
355 34780775
356 35804102
357 36857370
358 37938834
359 39051892
360 40194703
361 41370727
362 42578201
363 43820624
364 45096179
365 46408604
366 47755949
367 49142036
368 50565037
369 52028808
370 53531426
371 55077024
372 56663576
373 58295296
374 59970253
375 61692717
376 63460698
377 65278749
378 67144740
379 69063329
380 71032528
381 73057047
382 75134801
383 77270821
384 79462916
385 81716223
386 84028662
387 86405453
388 88844457
389 91351222
390 93923464
391 96566866
392 99279311
393 102066558
394 104926392
395 107864947
396 110879901
397 113977524
398 117155631
399 120420601
400 123770196
401 127211183
402 130741173
403 134367107
404 138086790
405 141907272
406 145826267
407 149851259
408 153979858
409 158219729
410 162568645
411 167034417
412 171614777
413 176317991
414 181141643
415 186094219
416 191173534
417 196388224
418 201736021
419 207226074
420 212856022
421 218635238
422 224561567
423 230644579
424 236882090
425 243284207
426 249848607
427 256585679
428 263493375
429 270582288
430 277850304
431 285308622
432 292955046
433 300801069
434 308844750
435 317097836
436 325558388
437 334238788
438 343136975
439 352265683
440 361623188
441 371222501
442 381061855
443 391154977
444 401500048
445 412111169
446 422986836
447 434141488
448 445573658
449 457298542
450 469314579
451 481637411
452 494265891
453 507216020
454 520486654
455 534094647
456 548038838
457 562336560
458 576987050
459 592008079
460 607398974
461 623178409
462 639345664
463 655919976
464 672901133
465 690308848
466 708142969
467 726424223
468 745152504
469 764349148
470 784014548
471 804170609
472 824817890
473 845979377
474 867655646
475 889870397
476 912624838
477 935943284
478 959827089
479 984301782
480 1009368844
481 1035054579
482 1061361102
483 1088315451
484 1115920004
485 1144203103
486 1173167239
487 1202841651
488 1233229616
489 1264361174
490 1296239864
491 1328897182
492 1362336911
493 1396591529
494 1431665624
495 1467592613
496 1504377489
497 1542055243
498 1580631105
499 1620141205
500 1660591756
501 1702019918
502 1744432320
503 1787867880
504 1832333632
505 1877869734
506 1924484241
507 1972218517
508 2021081208
509 2071115576
510 2122330688
511 2174771239
512 2228447526
513 2283405575
514 2339656304
515 2397247866
516 2456191790
517 2516537802
518 2578298736
519 2641525851
520 2706232813
521 2772473194
522 2840261316
523 2909652551
524 2980662778
525 3053349067
526 3127728193
527 3203859809
528 3281761581
529 3361495149
530 3443079835
531 3526579236
532 3612013830
533 3699450022
534 3788909262
535 3880460226
536 3974126325
537 4069978403
538 4168041124
539 4268388479
540 4371046391
541 4476091356
542 4583551407
543 4693505524
544 4805983310
545 4921067178
546 5038788121
547 5159231401
548 5282430492
549 5408473413
550 5537395360
551 5669288189
552 5804188836
553 5942192319
554 6083338254
555 6227724810
556 6375393711
557 6526447327
558 6680929311
559 6838945618
560 7000543035
561 7165831013
562 7334858669
563 7507740151
564 7684526937
565 7865337147
566 8050225676
567 8239314629
568 8432661697
569 8630394142
570 8832572285
571 9039327887
572 9250725228
573 9466900500
574 9687921094
575 9913928955
576 10144994640
577 10381265091
578 10622815199
579 10869796935
580 11122288884
581 11380449348
582 11644360442
583 11914186113
584 12190013480
585 12472012092
586 12760273170
587 13054973333
588 13356208001
589 13664160060
590 13978930433
591 14300708347
592 14629599550
593 14965801058
594 15309423307
595 15660670391
596 16019659063
597 16386600476
598 16761616767
599 17144927782
600 17536661165
601 17937044630
602 18346212793
603 18764401342
604 19191751166
605 19628507546
606 20074817534
607 20530935270
608 20997015780
609 21473322096
610 21960016237
611 22457371945
612 22965558421
613 23484859258
614 24015452476
615 24557631685
616 25111583013
617 25677611898
618 26255912505
619 26846801352
620 27450482659
621 28067284109
622 28697418972
623 29341228132
624 29998934152
625 30670890251
626 31357330127
627 32058619567
628 32775002685
629 33506859865
630 34254445636
631 35018154223
632 35798252815
633 36595149644
634 37409123540
635 38240599012
636 39089866866
637 39957367022
638 40843404326
639 41748434442
640 42672775547
641 43616901325
642 44581143357
643 45565992613
644 46571796596
645 47599063812
646 48648156665
647 49719603754
648 50813782825
649 51931241712
650 53072375842
651 54237752737
652 55427784816
653 56643061857
654 57884013453
655 59151250930
656 60445223875
657 61766565549
658 63115744534
659 64493418889
660 65900076770
661 67336400224
662 68802899628
663 70300281610
664 71829078133
665 73390023319
666 74983671024
667 76610782215
668 78271935824
669 79967920200
670 81699338395
671 83467009377
672 85271561076
673 87113842331
674 88994508950
675 90914440435
676 92874319920
677 94875060851
678 96917374181
679 99002206759
680 101130300931
681 103302637692
682 105519989908
683 107783376377
684 110093601466
685 112451721131
686 114858574665
687 117315256201
688 119822639524
689 122381860692
690 124993828689
691 127659721084
692 130380486122
693 133157343878
694 135991281100
695 138883564529
696 141835220667
697 144847562432
698 147921659991
699 151058873749
700 154260317289
701 157527402763
702 160861288162
703 164263437170
704 167735056789
705 171277663548
706 174892512891
707 178581178931
708 182344967138
709 186185508930
710 190104164295
711 194102623632
712 198182301421
713 202344951929
714 206592045480
715 210925400239
716 215346547632
717 219857371434
718 224459463843
719 229154779659
720 233944973867
721 238832072306
722 243817797904
723 248904249665
724 254093218762
725 259386882966
726 264787103485
727 270296137239
728 275915921492
729 281648794511
730 287496769618
731 293462272644
732 299547395504
733 305754651981
734 312086218547
735 318544699629
736 325132356950
737 331851892041
738 338705654236
739 345696442988
740 352826702149
741 360099331906
742 367516871087
743 375082327756
744 382798338894
745 390668021338
746 398694117125
747 406879855237
748 415228084003
749 423742152025
750 432425016957
751 441280148419
752 450310621364
753 459520029989
754 468911567565
755 478488961128
756 488255526256
757 498215124338
758 508371201280
759 518727757053
760 529288369808
761 540057186763
762 551037922203
763 562234872729
764 573651897977
765 585293448415
766 597163530796
767 609266759028
768 621607291935
769 634189909206
770 647018931097
771 660099308332
772 673435525380
773 687032714087
774 700895528083
775 715029283390
776 729438813495
777 744129624237
778 759106731657
779 774375842535
780 789942161638
781 805811600040
782 821989562171
783 838482169951
784 855295031340
785 872434490863
786 889906366258
787 907717228883
788 925873118713
789 944380840961
790 963246661732
791 982477633082
792 1002080254870
793 1022061830648
794 1042429106861
795 1063189646651
796 1084350448288
797 1105919348275
798 1127903604551
799 1150311332653
800 1173150064740
801 1196428204138
802 1220153562596
803 1244334846405
804 1268980156349
805 1294098507948
806 1319698306091
807 1345788885537
808 1372378962218
809 1399478206290
810 1427095654525
811 1455241319960
812 1483924577269
813 1513155793196
814 1542944687547
815 1573301998593
816 1604237802901
817 1635763218525
818 1667888696564
819 1700625747202
820 1733985205099
821 1767978991576
822 1802618337056
823 1837915583717
824 1873882377771
825 1910531495647
826 1947875008891
827 1985926149114
828 2024697427511
829 2064202541611
830 2104454463241
831 2145467371017
832 2187254709043
833 2229831159449
834 2273210653714
835 2317408389964
836 2362438810652
837 2408317646395
838 2455059863006
839 2502681748273
840 2551198808951
841 2600627903777
842 2650985105274
843 2702287861753
844 2754552826353
845 2807798063441
846 2862040825441
847 2917299808661
848 2973592892640
849 3030939425912
850 3089357931037
851 3148868437914
852 3209490133667
853 3271243747078
854 3334149159283
855 3398227820752
856 3463500325403
857 3529988876757
858 3597714804499
859 3666701085244
860 3736969817374
861 3808544775471
862 3881448846815
863 3955706638443
864 4031341852891
865 4108379951758
866 4186845487785
867 4266764805013
868 4348163329999
869 4431068326388
870 4515506122788
871 4601504927597
872 4689092010469
873 4778296554997
874 4869146797369
875 4961672937245
876 5055904209526
877 5151871857653
878 5249606156806
879 5349139428227
880 5450503016842
881 5553730365844
882 5658853924527
883 5765908289362
884 5874927060285
885 5985946024238
886 6098999963724
887 6214125904665
888 6331359851372
889 6450740103303
890 6572303936034
891 6696090964016
892 6822139770736
893 6950491338109
894 7081185599853
895 7214264944252
896 7349770710242
897 7487746737804
898 7628235810863
899 7771283278756
900 7916933418175
901 8065233130657
902 8216228244598
903 8369967264192
904 8526497614873
905 8685869465942
906 8848131891528
907 9013336774109
908 9181534901907
909 9352779925764
910 9527124397315
911 9704623804345
912 9885332519975
913 10069307921883
914 10256606274953
915 10447286908037
916 10641408033687
917 10839031006326
918 11040216049086
919 11245026601153
920 11453524974109
921 11665776758970
922 11881846416653
923 12101801771672
924 12325709504791
925 12553639739168
926 12785661459274
927 13021847161278
928 13262268202042
929 13506999539420
930 13756114979169
931 14009692013500
932 14267806989836
933 14530540016124
934 14797970056362
935 15070179931538
936 15347251307706
937 15629269798836
938 15916319873152
939 16208490027689
940 16505867617006
941 16808544126967
942 17116609891334
943 17430159473729
944 17749286297735
945 18074088103370
946 18404661495857
947 18741107507627
948 19083526029062
949 19432021482778
950 19786697163875
951 20147660994180
952 20515019776346
953 20888885057599
954 21269367260718
955 21656581666889
956 22050642450964
957 22451668747432
958 22859778595502
959 23275095121367
960 23697740353743
961 24127841529828
962 24565524810680
963 25010921676262
964 25464162545313
965 25925383291176
966 26394718726541
967 26872309250327
968 27358294226608
969 27852818724148
970 28356026795315
971 28868068343818
972 29389092261523
973 29919253432305
974 30458705758139
975 31007609262144
976 31566123008853
977 32134412340424
978 32712641648643
979 33300981755357
980 33899602567529
981 34508680560820
982 35128391323922
983 35758917183356
984 36400439591954
985 37053146903475
986 37717226638747
987 38392873370597
988 39080280872859
989 39779650152075
990 40491181433917
991 41215082353474
992 41951559812541
993 42700828284719
994 43463101550131
995 44238601156028
996 45027547980697
997 45830170858850
998 46646698010475
999 47477365788813
1000 48322409979680