0 1
1 1
2 3
3 4
4 8
5 11
6 18
7 24
8 36
9 47
10 66
11 84
12 113
13 141
14 183
15 225
16 284
17 344
18 425
19 508
20 617
21 729
22 872
23 1020
24 1205
25 1397
26 1632
27 1877
28 2172
29 2480
30 2846
31 3228
32 3677
33 4146
34 4691
35 5261
36 5917
37 6603
38 7386
39 8205
40 9133
41 10103
42 11195
43 12336
44 13613
45 14947
46 16431
47 17981
48 19697
49 21488
50 23462
51 25521
52 27781
53 30137
54 32713
55 35397
56 38321
57 41366
58 44672
59 48113
60 51838
61 55712
62 59894
63 64241
64 68921
65 73783
66 79004
67 84425
68 90233
69 96260
70 102703
71 109385
72 116514
73 123903
74 131771
75 139922
76 148585
77 157555
78 167072
79 176921
80 187354
81 198145
82 209558
83 221357
84 233818
85 246694
86 260273
87 274298
88 289069
89 304318
90 320358
91 336909
92 354298
93 372233
94 391054
95 410458
96 430798
97 451759
98 473708
99 496318
100 519970
101 544324
102 569776
103 595973
104 623326
105 651469
106 680827
107 711022
108 742494
109 774851
110 808549
111 843182
112 879222
113 916249
114 954751
115 994294
116 1035382
117 1077567
118 1121369
119 1166326
120 1212975
121 1260838
122 1310470
123 1361378
124 1414134
125 1468230
126 1524255
127 1581686
128 1641130
129 1702048
130 1765065
131 1829626
132 1896375
133 1964740
134 2035384
135 2107719
136 2182426
137 2258901
138 2337844
139 2418634
140 2501991
141 2587276
142 2675229
143 2765194
144 2857931
145 2952766
146 3050479
147 3150379
148 3253266
149 3358431
150 3466695
151 3577330
152 3691179
153 3807495
154 3927142
155 4049355
156 4175019
157 4303350
158 4435255
159 4569931
160 4708307
161 4849560
162 4994642
163 5142710
164 5294739
165 5449866
166 5609088
167 5771523
168 5938191
169 6108189
170 6282561
171 6460383
172 6642723
173 6828636
174 7019214
175 7213491
176 7412583
177 7615503
178 7823391
179 8035239
180 8252212
181 8473279
182 8699631
183 8930215
184 9166247
185 9406652
186 9652671
187 9903207
188 10159527
189 10420511
190 10687452
191 10959207
192 11237096
193 11519952
194 11809122
195 12103416
196 12404207
197 12710282
198 13023041
199 13341247
200 13666328
201 13997022
202 14334785
203 14678331
204 15029144
205 15385913
206 15750150
207 16120520
208 16498563
209 16882919
210 17275157
211 17673891
212 18080720
213 18494232
214 18916055
215 19344752
216 19781980
217 20226276
218 20679327
219 21139644
220 21608944
221 22085711
222 22571693
223 23065347
224 23568452
225 24079438
226 24600114
227 25128884
228 25667588
229 26214602
230 26771798
231 27337524
232 27913684
233 28498598
234 29094202
235 29698788
236 30314324
237 30939074
238 31575038
239 32220452
240 32877349
241 33543935
242 34222277
243 34910552
244 35610860
245 36321349
246 37044152
247 37777388
248 38523224
249 39279749
250 40049164
251 40829528
252 41623077
253 42427839
254 43246085
255 44075813
256 44919328
257 45774598
258 46643963
259 47525360
260 48421165
261 49329283
262 50252126
263 51187568
264 52138057
265 53101435
266 54080186
267 55072121
268 56079760
269 57100882
270 58138044
271 59188992
272 60256321
273 61337744
274 62435893
275 63548449
276 64678081
277 65822437
278 66984224
279 68161057
280 69355681
281 70565677
282 71793829
283 73037684
284 74300065
285 75578485
286 76875805
287 78189505
288 79522485
289 80872190
290 82241560
291 83628005
292 85034505
293 86458435
294 87902815
295 89364985
296 90848005
297 92349180
298 93871610
299 95412565
300 96975186
301 98556706
302 100160308
303 101783189
304 103428573
305 105093621
306 106781598
307 108489629
308 110221021
309 111972862
310 113748501
311 115544989
312 117365718
313 119207701
314 121074373
315 122962710
316 124876189
317 126811749
318 128772910
319 130756573
320 132766302
321 134798959
322 136858152
323 138940705
324 141050270
325 143183632
326 145344487
327 147529582
328 149742657
329 151980420
330 154246656
331 156538033
332 158858382
333 161204331
334 163579756
335 165981246
336 168412722
337 170870733
338 173359246
339 175874770
340 178421318
341 180995358
342 183600950
343 186234521
344 188900178
345 191594307
346 194321061
347 197076786
348 199865682
349 202684053
350 205536147
351 208418226
352 211334586
353 214281447
354 217263153
355 220275882
356 223324026
357 226403721
358 229519407
359 232667178
360 235851523
361 239068492
362 242322624
363 245609926
364 248934986
365 252293768
366 255690909
367 259122330
368 262592718
369 266097950
370 269642763
371 273222990
372 276843419
373 280499838
374 284197086
375 287930907
376 291706190
377 295518635
378 299373182
379 303265486
380 307200539
381 311173950
382 315190763
383 319246542
384 323346383
385 327485804
386 331669953
387 335894303
388 340164054
389 344474633
390 348831293
391 353229414
392 357674303
393 362161293
394 366695744
395 371272943
396 375898303
397 380567064
398 385284693
399 390046383
400 394857655
401 399713654
402 404619956
403 409571658
404 414574391
405 419623204
406 424723782
407 429871127
408 435070979
409 440318291
410 445618859
411 450967587
412 456370327
413 461821934
414 467328316
415 472884279
416 478495787
417 484157597
418 489875729
419 495644891
420 501471160
421 507349193
422 513285125
423 519273563
424 525320699
425 531421090
426 537580985
427 543794891
428 550069115
429 556398113
430 562788250
431 569233931
432 575741580
433 582305550
434 588932324
435 595616204
436 602363731
437 609169156
438 616039079
439 622967699
440 629961676
441 637015156
442 644134859
443 651314879
444 658561996
445 665870251
446 673246484
447 680684684
448 688191751
449 695761621
450 703401255
451 711104535
452 718878484
453 726716930
454 734626957
455 742602340
456 750650224
457 758764330
458 766951865
459 775206496
460 783535492
461 791932465
462 800404747
463 808945895
464 817563304
465 826250476
466 835014868
467 843849928
468 852763176
469 861748004
470 870811996
471 879948488
472 889165128
473 898455196
474 907826404
475 917271976
476 926799688
477 936402708
478 946088876
479 955851304
480 965697897
481 975621709
482 985630711
483 995717900
484 1005891312
485 1016143887
486 1026483726
487 1036903712
488 1047412012
489 1058001451
490 1068680262
491 1079441212
492 1090292601
493 1101227137
494 1112253187
495 1123363401
496 1134566212
497 1145854212
498 1157235901
499 1168703812
500 1180266513
501 1191916477
502 1203662340
503 1215496516
504 1227427709
505 1239448273
506 1251566980
507 1263776125
508 1276084548
509 1288484484
510 1300984842
511 1313577796
512 1326272325
513 1339060542
514 1351951495
515 1364937237
516 1378026885
517 1391212431
518 1404503062
519 1417890709
520 1431384629
521 1444976691
522 1458676223
523 1472475032
524 1486382517
525 1500390423
526 1514508219
527 1528727589
528 1543058073
529 1557491292
530 1572036858
531 1586686329
532 1601449389
533 1616317533
534 1631300517
535 1646389773
536 1661595129
537 1676907954
538 1692338148
539 1707877017
540 1723534534
541 1739301940
542 1755189282
543 1771187737
544 1787307425
545 1803539459
546 1819894032
547 1836362193
548 1852954209
549 1869661064
550 1886493099
551 1903441233
552 1920515882
553 1937707899
554 1955027775
555 1972466298
556 1990034033
557 2007721703
558 2025539948
559 2043479425
560 2061550850
561 2079744813
562 2098072106
563 2116523253
564 2135109122
565 2153820170
566 2172667341
567 2191641026
568 2210752245
569 2229991322
570 2249369354
571 2268876597
572 2288524226
573 2308302429
574 2328222458
575 2348274434
576 2368469686
577 2388798267
578 2409271584
579 2429879622
580 2450633866
581 2471524232
582 2492562284
583 2513737869
584 2535062630
585 2556526345
586 2578140735
587 2599895510
588 2621802470
589 2643851255
590 2666053745
591 2688399510
592 2710900510
593 2733546245
594 2756348755
595 2779297470
596 2802404510
597 2825659235
598 2849073845
599 2872637630
600 2896362871
601 2920238786
602 2944277738
603 2968468874
604 2992824638
605 3017334106
606 3042009803
607 3066840734
608 3091839506
609 3116995052
610 3142320061
611 3167803394
612 3193457823
613 3219272136
614 3245259188
615 3271407695
616 3297730594
617 3324216529
618 3350878520
619 3377705138
620 3404709487
621 3431880064
622 3459230057
623 3486747890
624 3514446835
625 3542315242
626 3570366467
627 3598588787
628 3626995642
629 3655575235
630 3684341091
631 3713281338
632 3742409587
633 3771713891
634 3801207946
635 3830879731
636 3860743027
637 3890785738
638 3921021731
639 3951438835
640 3982051003
641 4012845988
642 4043837830
643 4075014206
644 4106389243
645 4137950542
646 4169712316
647 4201662091
648 4233814167
649 4266155993
650 4298701957
651 4331439431
652 4364382891
653 4397519632
654 4430864218
655 4464403867
656 4498153231
657 4532099451
658 4566257267
659 4600613743
660 4635183708
661 4669954147
662 4704939979
663 4740128111
664 4775533551
665 4811143128
666 4846971939
667 4883006735
668 4919262703
669 4955726515
670 4992413448
671 5029310095
672 5066431824
673 5103765148
674 5141325526
675 5179099392
676 5217102295
677 5255320590
678 5293769917
679 5332436551
680 5371336224
681 5410455130
682 5449809093
683 5489384227
684 5529196448
685 5569231789
686 5609506258
687 5650005808
688 5690746539
689 5731714323
690 5772925353
691 5814365419
692 5856050808
693 5897967228
694 5940131059
695 5982527928
696 6025174308
697 6068055744
698 6111188803
699 6154558948
700 6198182840
701 6242045859
702 6286164761
703 6330524843
704 6375142956
705 6420004314
706 6465125862
707 6510492732
708 6556121964
709 6601998606
710 6648139794
711 6694530492
712 6741187932
713 6788096994
714 6835275006
715 6882706764
716 6930409692
717 6978368502
718 7026600714
719 7075090956
720 7123856845
721 7172882923
722 7222186905
723 7271753248
724 7321599764
725 7371710825
726 7422104340
727 7472764596
728 7523709600
729 7574923553
730 7626424560
731 7678196736
732 7730258285
733 7782593235
734 7835219889
735 7888122189
736 7941318536
737 7994792786
738 8048563439
739 8102614264
740 8156963861
741 8211595911
742 8266529114
743 8321747064
744 8377268561
745 8433077111
746 8489191614
747 8545595489
748 8602307736
749 8659311686
750 8716626440
751 8774235240
752 8832157289
753 8890375740
754 8948909897
755 9007742825
756 9066893929
757 9126346185
758 9186119100
759 9246195561
760 9306595177
761 9367300745
762 9428331977
763 9489671580
764 9551339369
765 9613317961
766 9675627273
767 9738249833
768 9801205661
769 9864477194
770 9928084556
771 9992010093
772 10056274033
773 10120858631
774 10185784219
775 10251032961
776 10316625293
777 10382543288
778 10448807486
779 10515399869
780 10582341082
781 10649613014
782 10717236416
783 10785193085
784 10853503877
785 10922150497
786 10991153906
787 11060495717
788 11130196997
789 11200239266
790 11270643697
791 11341391717
792 11412504606
793 11483963697
794 11555790377
795 11627965886
796 11700511717
797 11773409017
798 11846679386
799 11920303877
800 11994304198
801 12068661307
802 12143397020
803 12218492201
804 12293968774
805 12369807508
806 12446030435
807 12522618230
808 12599593033
809 12676935424
810 12754667652
811 12832770201
812 12911265430
813 12990133727
814 13069397560
815 13149037222
816 13229075290
817 13309491961
818 13390309922
819 13471509274
820 13553112814
821 13635100546
822 13717495378
823 13800277217
824 13883469082
825 13967050783
826 14051045449
827 14135432794
828 14220236058
829 14305434857
830 14391052543
831 14477068634
832 14563506594
833 14650345843
834 14737609957
835 14825278258
836 14913374434
837 15001877709
838 15090811883
839 15180156082
840 15269934219
841 15360125320
842 15450753412
843 15541797422
844 15633281490
845 15725184444
846 15817530537
847 15910298498
848 16003512694
849 16097151754
850 16191240159
851 16285756438
852 16380725187
853 16476124834
854 16571980090
855 16668269283
856 16765017238
857 16862202183
858 16959849058
859 17057935990
860 17156488035
861 17255483218
862 17354946711
863 17454856438
864 17555237687
865 17656068280
866 17757373621
867 17859131431
868 17961367230
869 18064058637
870 18167231289
871 18270862702
872 18374978631
873 18479556489
874 18584622148
875 18690152919
876 18796174791
877 18902664972
878 19009649569
879 19117105687
880 19225059551
881 19333488162
882 19442417864
883 19551825554
884 19661737695
885 19772131080
886 19883032290
887 19994418015
888 20106314955
889 20218699695
890 20331599055
891 20444989515
892 20558898015
893 20673300930
894 20788225320
895 20903647455
896 21019594515
897 21136042665
898 21253019205
899 21370500195
900 21488513056
901 21607033741
902 21726089793
903 21845657059
904 21965763203
905 22086383966
906 22207547133
907 22329228339
908 22451455491
909 22574204117
910 22697502246
911 22821325299
912 22945701428
913 23070605946
914 23196067128
915 23322060180
916 23448613499
917 23575702184
918 23703354755
919 23831546203
920 23960305172
921 24089606544
922 24219479087
923 24349897575
924 24480890900
925 24612433727
926 24744555072
927 24877229492
928 25010486127
929 25144299425
930 25278698651
931 25413658143
932 25549207292
933 25685320326
934 25822026761
935 25959300716
936 26097171832
937 26235614118
938 26374657341
939 26514275400
940 26654498188
941 26795299493
942 26936709335
943 27078701391
944 27221305808
945 27364496152
946 27508302696
947 27652698896
948 27797715152
949 27943324808
950 28089558392
951 28236389136
952 28383847696
953 28531907192
954 28680598408
955 28829894352
956 28979825936
957 29130366056
958 29281545752
959 29433337808
960 29585773393
961 29738825177
962 29892524459
963 30046843796
964 30201814616
965 30357409363
966 30513659594
967 30670537640
968 30828075188
969 30986244455
970 31145077258
971 31304545700
972 31464681729
973 31625457333
974 31786904591
975 31948995377
976 32111761900
977 32275175920
978 32439269777
979 32604015116
980 32769444409
981 32935529185
982 33102302048
983 33269734412
984 33437859013
985 33606647149
986 33776131688
987 33946283813
988 34117136524
989 34288660888
990 34460890038
991 34633794924
992 34807408813
993 34981702538
994 35156709499
995 35332400413
996 35508808813
997 35685905299
998 35863723538
999 36042234013
1000 36221470525