0 1
1 1
2 2
3 7
4 18
5 41
6 85
7 162
8 287
9 478
10 756
11 1145
12 1672
13 2367
14 3263
15 4396
16 5805
17 7532
18 9622
19 12123
20 15086
21 18565
22 22617
23 27302
24 32683
25 38826
26 45800
27 53677
28 62532
29 72443
30 83491
31 95760
32 109337
33 124312
34 140778
35 158831
36 178570
37 200097
38 223517
39 248938
40 276471
41 306230
42 338332
43 372897
44 410048
45 449911
46 492615
47 538292
48 587077
49 639108
50 694526
51 753475
52 816102
53 882557
54 952993
55 1027566
56 1106435
57 1189762
58 1277712
59 1370453
60 1468156
61 1570995
62 1679147
63 1792792
64 1912113
65 2037296
66 2168530
67 2306007
68 2449922
69 2600473
70 2757861
71 2922290
72 3093967
73 3273102
74 3459908
75 3654601
76 3857400
77 4068527
78 4288207
79 4516668
80 4754141
81 5000860
82 5257062
83 5522987
84 5798878
85 6084981
86 6381545
87 6688822
88 7007067
89 7336538
90 7677496
91 8030205
92 8394932
93 8771947
94 9161523
95 9563936
96 9979465
97 10408392
98 10851002
99 11307583
100 11778426
101 12263825
102 12764077
103 13279482
104 13810343
105 14356966
106 14919660
107 15498737
108 16094512
109 16707303
110 17337431
111 17985220
112 18650997
113 19335092
114 20037838
115 20759571
116 21500630
117 22261357
118 23042097
119 23843198
120 24665011
121 25507890
122 26372192
123 27258277
124 28166508
125 29097251
126 30050875
127 31027752
128 32028257
129 33052768
130 34101666
131 35175335
132 36274162
133 37398537
134 38548853
135 39725506
136 40928895
137 42159422
138 43417492
139 44703513
140 46017896
141 47361055
142 48733407
143 50135372
144 51567373
145 53029836
146 54523190
147 56047867
148 57604302
149 59192933
150 60814201
151 62468550
152 64156427
153 65878282
154 67634568
155 69425741
156 71252260
157 73114587
158 75013187
159 76948528
160 78921081
161 80931320
162 82979722
163 85066767
164 87192938
165 89358721
166 91564605
167 93811082
168 96098647
169 98427798
170 100799036
171 103212865
172 105669792
173 108170327
174 110714983
175 113304276
176 115938725
177 118618852
178 121345182
179 124118243
180 126938566
181 129806685
182 132723137
183 135688462
184 138703203
185 141767906
186 144883120
187 148049397
188 151267292
189 154537363
190 157860171
191 161236280
192 164666257
193 168150672
194 171690098
195 175285111
196 178936290
197 182644217
198 186409477
199 190232658
200 194114351
201 198055150
202 202055652
203 206116457
204 210238168
205 214421391
206 218666735
207 222974812
208 227346237
209 231781628
210 236281606
211 240846795
212 245477822
213 250175317
214 254939913
215 259772246
216 264672955
217 269642682
218 274682072
219 279791773
220 284972436
221 290224715
222 295549267
223 300946752
224 306417833
225 311963176
226 317583450
227 323279327
228 329051482
229 334900593
230 340827341
231 346832410
232 352916487
233 359080262
234 365324428
235 371649681
236 378056720
237 384546247
238 391118967
239 397775588
240 404516821
241 411343380
242 418255982
243 425255347
244 432342198
245 439517261
246 446781265
247 454134942
248 461579027
249 469114258
250 476741376
251 484461125
252 492274252
253 500181507
254 508183643
255 516281416
256 524475585
257 532766912
258 541156162
259 549644103
260 558231506
261 566919145
262 575707797
263 584598242
264 593591263
265 602687646
266 611888180
267 621193657
268 630604872
269 640122623
270 649747711
271 659480940
272 669323117
273 679275052
274 689337558
275 699511451
276 709797550
277 720196677
278 730709657
279 741337318
280 752080491
281 762940010
282 773916712
283 785011437
284 796225028
285 807558331
286 819012195
287 830587472
288 842285017
289 854105688
290 866050346
291 878119855
292 890315082
293 902636897
294 915086173
295 927663786
296 940370615
297 953207542
298 966175452
299 979275233
300 992507776
301 1005873975
302 1019374727
303 1033010932
304 1046783493
305 1060693316
306 1074741310
307 1088928387
308 1103255462
309 1117723453
310 1132333281
311 1147085870
312 1161982147
313 1177023042
314 1192209488
315 1207542421
316 1223022780
317 1238651507
318 1254429547
319 1270357848
320 1286437361
321 1302669040
322 1319053842
323 1335592727
324 1352286658
325 1369136601
326 1386143525
327 1403308402
328 1420632207
329 1438115918
330 1455760516
331 1473566985
332 1491536312
333 1509669487
334 1527967503
335 1546431356
336 1565062045
337 1583860572
338 1602827942
339 1621965163
340 1641273246
341 1660753205
342 1680406057
343 1700232822
344 1720234523
345 1740412186
346 1760766840
347 1781299517
348 1802011252
349 1822903083
350 1843976051
351 1865231200
352 1886669577
353 1908292232
354 1930100218
355 1952094591
356 1974276410
357 1996646737
358 2019206637
359 2041957178
360 2064899431
361 2088034470
362 2111363372
363 2134887217
364 2158607088
365 2182524071
366 2206639255
367 2230953732
368 2255468597
369 2280184948
370 2305103886
371 2330226515
372 2355553942
373 2381087277
374 2406827633
375 2432776126
376 2458933875
377 2485302002
378 2511881632
379 2538673893
380 2565679916
381 2592900835
382 2620337787
383 2647991912
384 2675864353
385 2703956256
386 2732268770
387 2760803047
388 2789560242
389 2818541513
390 2847748021
391 2877180930
392 2906841407
393 2936730622
394 2966849748
395 2997199961
396 3027782440
397 3058598367
398 3089648927
399 3120935308
400 3152458701
401 3184220300
402 3216221302
403 3248462907
404 3280946318
405 3313672741
406 3346643385
407 3379859462
408 3413322187
409 3447032778
410 3480992456
411 3515202445
412 3549663972
413 3584378267
414 3619346563
415 3654570096
416 3690050105
417 3725787832
418 3761784522
419 3798041423
420 3834559786
421 3871340865
422 3908385917
423 3945696202
424 3983272983
425 4021117526
426 4059231100
427 4097614977
428 4136270432
429 4175198743
430 4214401191
431 4253879060
432 4293633637
433 4333666212
434 4373978078
435 4414570531
436 4455444870
437 4496602397
438 4538044417
439 4579772238
440 4621787171
441 4664090530
442 4706683632
443 4749567797
444 4792744348
445 4836214611
446 4879979915
447 4924041592
448 4968400977
449 5013059408
450 5058018226
451 5103278775
452 5148842402
453 5194710457
454 5240884293
455 5287365266
456 5334154735
457 5381254062
458 5428664612
459 5476387753
460 5524424856
461 5572777295
462 5621446447
463 5670433692
464 5719740413
465 5769367996
466 5819317830
467 5869591307
468 5920189822
469 5971114773
470 6022367561
471 6073949590
472 6125862267
473 6178107002
474 6230685208
475 6283598301
476 6336847700
477 6390434827
478 6444361107
479 6498627968
480 6553236841
481 6608189160
482 6663486362
483 6719129887
484 6775121178
485 6831461681
486 6888152845
487 6945196122
488 7002592967
489 7060344838
490 7118453196
491 7176919505
492 7235745232
493 7294931847
494 7354480823
495 7414393636
496 7474671765
497 7535316692
498 7596329902
499 7657712883
500 7719467126
501 7781594125
502 7844095377
503 7906972382
504 7970226643
505 8033859666
506 8097872960
507 8162268037
508 8227046412
509 8292209603
510 8357759131
511 8423696520
512 8490023297
513 8556740992
514 8623851138
515 8691355271
516 8759254930
517 8827551657
518 8896246997
519 8965342498
520 9034839711
521 9104740190
522 9175045492
523 9245757177
524 9316876808
525 9388405951
526 9460346175
527 9532699052
528 9605466157
529 9678649068
530 9752249366
531 9826268635
532 9900708462
533 9975570437
534 10050856153
535 10126567206
536 10202705195
537 10279271722
538 10356268392
539 10433696813
540 10511558596
541 10589855355
542 10668588707
543 10747760272
544 10827371673
545 10907424536
546 10987920490
547 11068861167
548 11150248202
549 11232083233
550 11314367901
551 11397103850
552 11480292727
553 11563936182
554 11648035868
555 11732593441
556 11817610560
557 11903088887
558 11989030087
559 12075435828
560 12162307781
561 12249647620
562 12337457022
563 12425737667
564 12514491238
565 12603719421
566 12693423905
567 12783606382
568 12874268547
569 12965412098
570 13057038736
571 13149150165
572 13241748092
573 13334834227
574 13428410283
575 13522477976
576 13617039025
577 13712095152
578 13807648082
579 13903699543
580 14000251266
581 14097304985
582 14194862437
583 14292925362
584 14391495503
585 14490574606
586 14590164420
587 14690266697
588 14790883192
589 14892015663
590 14993665871
591 15095835580
592 15198526557
593 15301740572
594 15405479398
595 15509744811
596 15614538590
597 15719862517
598 15825718377
599 15932107958
600 16039033051
601 16146495450
602 16254496952
603 16363039357
604 16472124468
605 16581754091
606 16691930035
607 16802654112
608 16913928137
609 17025753928
610 17138133306
611 17251068095
612 17364560122
613 17478611217
614 17593223213
615 17708397946
616 17824137255
617 17940442982
618 18057316972
619 18174761073
620 18292777136
621 18411367015
622 18530532567
623 18650275652
624 18770598133
625 18891501876
626 19012988750
627 19135060627
628 19257719382
629 19380966893
630 19504805041
631 19629235710
632 19754260787
633 19879882162
634 20006101728
635 20132921381
636 20260343020
637 20388368547
638 20516999867
639 20646238888
640 20776087521
641 20906547680
642 21037621282
643 21169310247
644 21301616498
645 21434541961
646 21568088565
647 21702258242
648 21837052927
649 21972474558
650 22108525076
651 22245206425
652 22382520552
653 22520469407
654 22659054943
655 22798279116
656 22938143885
657 23078651212
658 23219803062
659 23361601403
660 23504048206
661 23647145445
662 23790895097
663 23935299142
664 24080359563
665 24226078346
666 24372457480
667 24519498957
668 24667204772
669 24815576923
670 24964617411
671 25114328240
672 25264711417
673 25415768952
674 25567502858
675 25719915151
676 25873007850
677 26026782977
678 26181242557
679 26336388618
680 26492223191
681 26648748310
682 26805966012
683 26963878337
684 27122487328
685 27281795031
686 27441803495
687 27602514772
688 27763930917
689 27926053988
690 28088886046
691 28252429155
692 28416685382
693 28581656797
694 28747345473
695 28913753486
696 29080882915
697 29248735842
698 29417314352
699 29586620533
700 29756656476
701 29927424275
702 30098926027
703 30271163832
704 30444139793
705 30617856016
706 30792314610
707 30967517687
708 31143467362
709 31320165753
710 31497614981
711 31675817170
712 31854774447
713 32034488942
714 32214962788
715 32396198121
716 32578197080
717 32760961807
718 32944494447
719 33128797148
720 33313872061
721 33499721340
722 33686347142
723 33873751627
724 34061936958
725 34250905301
726 34440658825
727 34631199702
728 34822530107
729 35014652218
730 35207568216
731 35401280285
732 35595790612
733 35791101387
734 35987214803
735 36184133056
736 36381858345
737 36580392872
738 36779738842
739 36979898463
740 37180873946
741 37382667505
742 37585281357
743 37788717722
744 37992978823
745 38198066886
746 38403984140
747 38610732817
748 38818315152
749 39026733383
750 39235989751
751 39446086500
752 39657025877
753 39868810132
754 40081441518
755 40294922291
756 40509254710
757 40724441037
758 40940483537
759 41157384478
760 41375146131
761 41593770770
762 41813260672
763 42033618117
764 42254845388
765 42476944771
766 42699918555
767 42923769032
768 43148498497
769 43374109248
770 43600603586
771 43827983815
772 44056252242
773 44285411177
774 44515462933
775 44746409826
776 44978254175
777 45210998302
778 45444644532
779 45679195193
780 45914652616
781 46151019135
782 46388297087
783 46626488812
784 46865596653
785 47105622956
786 47346570070
787 47588440347
788 47831236142
789 48074959813
790 48319613721
791 48565200230
792 48811721707
793 49059180522
794 49307579048
795 49556919661
796 49807204740
797 50058436667
798 50310617827
799 50563750608
800 50817837401
801 51072880600
802 51328882602
803 51585845807
804 51843772618
805 52102665441
806 52362526685
807 52623358762
808 52885164087
809 53147945078
810 53411704156
811 53676443745
812 53942166272
813 54208874167
814 54476569863
815 54745255796
816 55014934405
817 55285608132
818 55557279422
819 55829950723
820 56103624486
821 56378303165
822 56653989217
823 56930685102
824 57208393283
825 57487116226
826 57766856400
827 58047616277
828 58329398332
829 58612205043
830 58896038891
831 59180902360
832 59466797937
833 59753728112
834 60041695378
835 60330702231
836 60620751170
837 60911844697
838 61203985317
839 61497175538
840 61791417871
841 62086714830
842 62383068932
843 62680482697
844 62978958648
845 63278499311
846 63579107215
847 63880784892
848 64183534877
849 64487359708
850 64792261926
851 65098244075
852 65405308702
853 65713458357
854 66022695593
855 66333022966
856 66644443035
857 66956958362
858 67270571512
859 67585285053
860 67901101556
861 68218023595
862 68536053747
863 68855194592
864 69175448713
865 69496818696
866 69819307130
867 70142916607
868 70467649722
869 70793509073
870 71120497261
871 71448616890
872 71777870567
873 72108260902
874 72439790508
875 72772462001
876 73106278000
877 73441241127
878 73777354007
879 74114619268
880 74453039541
881 74792617460
882 75133355662
883 75475256787
884 75818323478
885 76162558381
886 76507964145
887 76854543422
888 77202298867
889 77551233138
890 77901348896
891 78252648805
892 78605135532
893 78958811747
894 79313680123
895 79669743336
896 80027004065
897 80385464992
898 80745128802
899 81105998183
900 81468075826
901 81831364425
902 82195866677
903 82561585282
904 82928522943
905 83296682366
906 83666066260
907 84036677337
908 84408518312
909 84781591903
910 85155900831
911 85531447820
912 85908235597
913 86286266892
914 86665544438
915 87046070971
916 87427849230
917 87810881957
918 88195171897
919 88580721798
920 88967534411
921 89355612490
922 89744958792
923 90135576077
924 90527467108
925 90920634651
926 91315081475
927 91710810352
928 92107824057
929 92506125368
930 92905717066
931 93306601935
932 93708782762
933 94112262337
934 94517043453
935 94923128906
936 95330521495
937 95739224022
938 96149239292
939 96560570113
940 96973219296
941 97387189655
942 97802484007
943 98219105172
944 98637055973
945 99056339236
946 99476957790
947 99898914467
948 100322212102
949 100746853533
950 101172841601
951 101600179150
952 102028869027
953 102458914082
954 102890317168
955 103323081141
956 103757208860
957 104192703187
958 104629566987
959 105067803128
960 105507414481
961 105948403920
962 106390774322
963 106834528567
964 107279669538
965 107726200121
966 108174123205
967 108623441682
968 109074158447
969 109526276398
970 109979798436
971 110434727465
972 110891066392
973 111348818127
974 111807985583
975 112268571676
976 112730579325
977 113194011452
978 113658870982
979 114125160843
980 114592883966
981 115062043285
982 115532641737
983 116004682262
984 116478167803
985 116953101306
986 117429485720
987 117907323997
988 118386619092
989 118867373963
990 119349591571
991 119833274880
992 120318426857
993 120805050472
994 121293148698
995 121782724511
996 122273780890
997 122766320817
998 123260347277
999 123755863258
1000 124252871751