0 1
1 1
2 1
3 1
4 2
5 2
6 2
7 2
8 4
9 5
10 5
11 5
12 7
13 8
14 8
15 8
16 12
17 14
18 15
19 15
20 19
21 21
22 22
23 22
24 28
25 33
26 35
27 37
28 43
29 48
30 50
31 52
32 61
33 69
34 74
35 78
36 90
37 98
38 103
39 107
40 122
41 135
42 143
43 152
44 170
45 186
46 194
47 203
48 225
49 247
50 261
51 275
52 305
53 330
54 348
55 362
56 396
57 429
58 454
59 477
60 519
61 561
62 590
63 618
64 666
65 717
66 756
67 794
68 856
69 916
70 966
71 1009
72 1083
73 1155
74 1217
75 1275
76 1365
77 1454
78 1527
79 1599
80 1703
81 1813
82 1902
83 1991
84 2118
85 2248
86 2358
87 2461
88 2613
89 2768
90 2905
91 3032
92 3210
93 3394
94 3555
95 3708
96 3913
97 4137
98 4331
99 4521
100 4764
101 5022
102 5252
103 5472
104 5757
105 6059
106 6341
107 6607
108 6947
109 7297
110 7621
111 7932
112 8321
113 8736
114 9119
115 9498
116 9957
117 10441
118 10884
119 11315
120 11841
121 12401
122 12929
123 13439
124 14063
125 14714
126 15326
127 15912
128 16615
129 17367
130 18080
131 18776
132 19594
133 20472
134 21296
135 22097
136 23024
137 24020
138 24977
139 25910
140 26991
141 28138
142 29246
143 30318
144 31546
145 32850
146 34115
147 35358
148 36771
149 38276
150 39727
151 41156
152 42761
153 44470
154 46127
155 47760
156 49599
157 51552
158 53453
159 55315
160 57406
161 59622
162 61789
163 63915
164 66286
165 68808
166 71275
167 73698
168 76376
169 79235
170 82041
171 84803
172 87837
173 91063
174 94245
175 97375
176 100801
177 104439
178 108051
179 111610
180 115487
181 119587
182 123654
183 127671
184 132028
185 136646
186 141237
187 145795
188 150715
189 155916
190 161075
191 166190
192 171701
193 177534
194 183347
195 189118
196 195333
197 201889
198 208419
199 214884
200 221816
201 229142
202 236469
203 243747
204 251527
205 259751
206 267965
207 276115
208 284781
209 293934
210 303116
211 312254
212 321963
213 332194
214 342477
215 352688
216 363503
217 374867
218 386315
219 397722
220 409793
221 422479
222 435247
223 447984
224 461407
225 475501
226 489683
227 503858
228 518794
229 534473
230 550270
231 566038
232 582637
233 600024
234 617563
235 635071
236 653479
237 672768
238 692241
239 711694
240 732082
241 753462
242 775038
243 796625
244 819191
245 842835
246 866733
247 890645
248 915617
249 941740
250 968205
251 994682
252 1022308
253 1051144
254 1080367
255 1109634
256 1140122
257 1171956
258 1204216
259 1236597
260 1270264
261 1305382
262 1340942
263 1376632
264 1413720
265 1452386
266 1491606
267 1530969
268 1571893
269 1614478
270 1657677
271 1700996
272 1745965
273 1792776
274 1840298
275 1888034
276 1937513
277 1989034
278 2041293
279 2093783
280 2148082
281 2204578
282 2261974
283 2319668
284 2379357
285 2441381
286 2504448
287 2567796
288 2633247
289 2701178
290 2770276
291 2839797
292 2911578
293 2986089
294 3061837
295 3138106
296 3216722
297 3298261
298 3381148
299 3464653
300 3550752
301 3639995
302 3730779
303 3822188
304 3916411
305 4013962
306 4113211
307 4213167
308 4316139
309 4422763
310 4531249
311 4640564
312 4753033
313 4869486
314 4987955
315 5107365
316 5230137
317 5357168
318 5486492
319 5616842
320 5750816
321 5889318
322 6030415
323 6172646
324 6318753
325 6469675
326 6623410
327 6778477
328 6937645
329 7102047
330 7269497
331 7438537
332 7611938
333 7790917
334 7973164
335 8157136
336 8345817
337 8540478
338 8738794
339 8939022
340 9144384
341 9356104
342 9571741
343 9789425
344 10012531
345 10242535
346 10476843
347 10713524
348 10955992
349 11205930
350 11460468
351 11717545
352 11980706
353 12251831
354 12528086
355 12807203
356 13092930
357 13387145
358 13686989
359 13989876
360 14299727
361 14618571
362 14943538
363 15272010
364 15607981
365 15953655
366 16305910
367 16662045
368 17026071
369 17400383
370 17781776
371 18167475
372 18561752
373 18967060
374 19380100
375 19797765
376 20224613
377 20663140
378 21109985
379 21561869
380 22023606
381 22497944
382 22981290
383 23470187
384 23969481
385 24482301
386 25004766
387 25533292
388 26072880
389 26626923
390 27191485
391 27762653
392 28345635
393 28943964
394 29553751
395 30170692
396 30800235
397 31446067
398 32104237
399 32770292
400 33449750
401 34146635
402 34856772
403 35575645
404 36308771
405 37060430
406 37826223
407 38601478
408 39391994
409 40202244
410 41027841
411 41863688
412 42716006
413 43589249
414 44478903
415 45379511
416 46297617
417 47238098
418 48196279
419 49166510
420 50155391
421 51168273
422 52200002
423 53244650
424 54308983
425 55398804
426 56509037
427 57633362
428 58778855
429 59951443
430 61146057
431 62355703
432 63587746
433 64848411
434 66132705
435 67433508
436 68758266
437 70113673
438 71494295
439 72892848
440 74316669
441 75772925
442 77256037
443 78758592
444 80288320
445 81852612
446 83445823
447 85059835
448 86702865
449 88382398
450 90092758
451 91825468
452 93589156
453 95391882
454 97227626
455 99087551
456 100980255
457 102914544
458 104883940
459 106879318
460 108909520
461 110983926
462 113096092
463 115236174
464 117413415
465 119637404
466 121901924
467 124196320
468 126530232
469 128913640
470 131340325
471 133799310
472 136300250
473 138853856
474 141453541
475 144088183
476 146767338
477 149502288
478 152286211
479 155107591
480 157976462
481 160904480
482 163884947
483 166905556
484 169976963
485 173110953
486 176300682
487 179533202
488 182819597
489 186172553
490 189584941
491 193043524
492 196559323
493 200146006
494 203795741
495 207494715
496 211254175
497 215088658
498 218990584
499 222945375
500 226964787
501 231063643
502 235234539
503 239461655
504 243757105
505 248136414
506 252592356
507 257108864
508 261698114
509 266376534
510 271136362
511 275961087
512 280862655
513 285858355
514 290940368
515 296091833
516 301325360
517 306658674
518 312084080
519 317583413
520 323169977
521 328861787
522 334651213
523 340519422
524 346480355
525 352553130
526 358729687
527 364990561
528 371349486
529 377826956
530 384414297
531 391091447
532 397872519
533 404779098
534 411802731
535 418922139
536 426151908
537 433514181
538 441000958
539 448589587
540 456295157
541 464140702
542 472118350
543 480204891
544 488415282
545 496773938
546 505272522
547 513887502
548 522633574
549 531536270
550 540587045
551 549761673
552 559075500
553 568554797
554 578191466
555 587959860
556 597876258
557 607967307
558 618224857
559 628622153
560 639176063
561 649914826
562 660830081
563 671894475
564 683124750
565 694550823
566 706163479
567 717934263
568 729880214
569 742032796
570 754383458
571 766902389
572 779607403
573 792530606
574 805663951
575 818975527
576 832483547
577 846221442
578 860181688
579 874331937
580 888690367
581 903292143
582 918129054
583 933167979
584 948426527
585 963941405
586 979704600
587 995682349
588 1011893234
589 1028374943
590 1045119841
591 1062092102
592 1079311106
593 1096815278
594 1114597243
595 1132620146
596 1150904219
597 1169489961
598 1188369552
599 1207505092
600 1226916299
601 1246645964
602 1266685644
603 1286996321
604 1307598275
605 1328536304
606 1349802655
607 1371356245
608 1393218000
609 1415433724
610 1437996673
611 1460863545
612 1484055856
613 1507621194
614 1531553332
615 1555807997
616 1580406397
617 1605398360
618 1630777408
619 1656498504
620 1682582452
621 1709080977
622 1735987776
623 1763256591
624 1790909118
625 1818998445
626 1847519243
627 1876423081
628 1905732814
629 1935502542
630 1965727131
631 1996356416
632 2027413985
633 2058956682
634 2090979352
635 2123430889
636 2156334532
637 2189750006
638 2223671285
639 2258045400
640 2292895892
641 2328285210
642 2364208625
643 2400611177
644 2437517296
645 2474990955
646 2513028413
647 2551571548
648 2590645054
649 2630315321
650 2670579834
651 2711379678
652 2752739477
653 2794728519
654 2837343844
655 2880525140
656 2924296009
657 2968728316
658 3013819833
659 3059509296
660 3105821652
661 3152830656
662 3200535158
663 3248870689
664 3297863184
665 3347587736
666 3398044109
667 3449166105
668 3500981011
669 3553567375
670 3606924955
671 3660985759
672 3715776233
673 3771378579
674 3827792106
675 3884947062
676 3942870538
677 4001648415
678 4061281449
679 4121696879
680 4182922471
681 4245046012
682 4308070255
683 4371918956
684 4436620651
685 4502266238
686 4568860000
687 4636324156
688 4704686565
689 4774041962
690 4844394603
691 4915665729
692 4987882119
693 5061142068
694 5135450567
695 5210727209
696 5286999815
697 5364369184
698 5442842333
699 5522335553
700 5602878253
701 5684573082
702 5767428178
703 5851357067
704 5936390277
705 6022634924
706 6110099723
707 6198696861
708 6288456047
709 6379489328
710 6471804660
711 6565311544
712 6660039842
713 6756106254
714 6853521423
715 6952191648
716 7052148299
717 7153510490
718 7256291477
719 7360392463
720 7465845212
721 7572772807
722 7681191132
723 7791000344
724 7902231794
725 8015013632
726 8129361669
727 8245174206
728 8362480574
729 8481413380
730 8601990287
731 8724108254
732 8847798562
733 8973197071
734 9100324097
735 9229071715
736 9359472556
737 9491664841
738 9625671032
739 9761380830
740 9898828587
741 10038158635
742 10179393879
743 10322421954
744 10467275274
745 10614104446
746 10762932288
747 10913643952
748 11066272781
749 11220975379
750 11377777988
751 11536561054
752 11697359020
753 11860331661
754 12025509141
755 12192766841
756 12362140042
757 12533794041
758 12707762155
759 12883917855
760 13062294993
761 13243065318
762 13426263001
763 13611760124
764 13799588911
765 13989926766
766 14182810472
767 14378109493
768 14575857818
769 14776236800
770 14979287570
771 15184874671
772 15393034338
773 15603951421
774 15817669633
775 16034050011
776 16253129862
777 16475101740
778 16700010982
779 16927717017
780 17158255905
781 17391827981
782 17628478930
783 17868064100
784 18110619888
785 18356354079
786 18605317600
787 18857361318
788 19112523665
789 19371017086
790 19632897141
791 19898007984
792 20166387780
793 20438256089
794 20713673353
795 20992482667
796 21274721380
797 21560617463
798 21850232700
799 22143407546
800 22440176368
801 22740774062
802 23045266888
803 23353493411
804 23665490990
805 23981500292
806 24301592694
807 24625600389
808 24953561952
809 25285722641
810 25622158105
811 25962697616
812 26307382281
813 26656467218
814 27010030583
815 27367898595
816 27730109947
817 28096929030
818 28468435905
819 28844453138
820 29225020953
821 29610413702
822 30000717965
823 30395750160
824 30795551733
825 31200402793
826 31610396859
827 32025343630
828 32445285455
829 32870511881
830 33301122889
831 33736925806
832 34177961027
833 34624528103
834 35076730285
835 35534373056
836 35997494459
837 36466403496
838 36941208999
839 37421713685
840 37907957563
841 38400256975
842 38898728240
843 39403168108
844 39913619269
845 40430404654
846 40953646236
847 41483136265
848 42018919328
849 42561330283
850 43110495610
851 43666205717
852 44228503497
853 44797736304
854 45374033121
855 45957179359
856 46547218196
857 47144509218
858 47749190820
859 48361042800
860 48980111238
861 49606763974
862 50241148298
863 50883034875
864 51532469690
865 52189831733
866 52855278031
867 53528578079
868 54209777157
869 54899267674
870 55597211136
871 56303374013
872 57017797127
873 57740884393
874 58472805788
875 59213326375
876 59962491097
877 60720713955
878 61488174950
879 62264630747
880 63050128353
881 63845089332
882 64649702461
883 65463721124
884 66287196170
885 67120565246
886 67964023197
887 68817320484
888 69680504260
889 70554027271
890 71438089061
891 72332436383
892 73237118420
893 74152604410
894 75079106072
895 76016362525
896 76964424999
897 77923772503
898 78894629362
899 79876726080
900 80870115495
901 81875291921
902 82892492244
903 83921444963
904 84962200103
905 86015268566
906 87080894216
907 88158804525
908 89249046033
909 90352145182
910 91468357374
911 92597407311
912 93739345149
913 94894709175
914 96063769074
915 97246241948
916 98442182449
917 99652139871
918 100876395603
919 102114662071
920 103366996845
921 104633968542
922 105915867975
923 107212406733
924 108523640304
925 109850157179
926 111192255296
927 112549640840
928 113922370204
929 115311051475
930 116715999713
931 118136914474
932 119573857235
933 121027449836
934 122498023742
935 123985267542
936 125489242646
937 127010589597
938 128549656937
939 130106134100
940 131680081455
941 133272161731
942 134882733452
943 136511483936
944 138158467645
945 139824365846
946 141509553365
947 143213717374
948 144936919180
949 146679856938
950 148442923921
951 150225797848
952 152028543174
953 153851871457
954 155696192344
955 157561181406
956 159446909290
957 161354113350
958 163283216254
959 165233891984
960 167206206803
961 169200921741
962 171218470724
963 173258524511
964 175321153678
965 177407145214
966 179516955602
967 181650247076
968 183807094279
969 185988300833
970 188194345404
971 190424880752
972 192679984536
973 194960485586
974 197266885355
975 199598836738
976 201956414520
977 204340473816
978 206751531152
979 209189240343
980 211653672632
981 214145708230
982 216665885396
983 219213857475
984 221789701688
985 224394318516
986 227028271410
987 229691206309
988 232383207612
989 235105195126
990 237857754094
991 240640527749
992 243453605607
993 246297938537
994 249174130393
995 252081826726
996 255021115566
997 257992979349
998 260998037925
999 264035932859
1000 267106755002