1 1
2 2
3 5
4 12
5 25
6 47
7 82
8 135
9 212
10 320
11 467
12 662
13 915
14 1237
15 1640
16 2137
17 2742
18 3470
19 4337
20 5360
21 6557
22 7947
23 9550
24 11387
25 13480
26 15852
27 18527
28 21530
29 24887
30 28625
31 32772
32 37357
33 42410
34 47962
35 54045
36 60692
37 67937
38 75815
39 84362
40 93615
41 103612
42 114392
43 125995
44 138462
45 151835
46 166157
47 181472
48 197825
49 215262
50 233830
51 253577
52 274552
53 296805
54 320387
55 345350
56 371747
57 399632
58 429060
59 460087
60 492770
61 527167
62 563337
63 601340
64 641237
65 683090
66 726962
67 772917
68 821020
69 871337
70 923935
71 978882
72 1036247
73 1096100
74 1158512
75 1223555
76 1291302
77 1361827
78 1435205
79 1511512
80 1590825
81 1673222
82 1758782
83 1847585
84 1939712
85 2035245
86 2134267
87 2236862
88 2343115
89 2453112
90 2566940
91 2684687
92 2806442
93 2932295
94 3062337
95 3196660
96 3335357
97 3478522
98 3626250
99 3778637
100 3935780
101 4097777
102 4264727
103 4436730
104 4613887
105 4796300
106 4984072
107 5177307
108 5376110
109 5580587
110 5790845
111 6006992
112 6229137
113 6457390
114 6691862
115 6932665
116 7179912
117 7433717
118 7694195
119 7961462
120 8235635
121 8516832
122 8805172
123 9100775
124 9403762
125 9714255
126 10032377
127 10358252
128 10692005
129 11033762
130 11383650
131 11741797
132 12108332
133 12483385
134 12867087
135 13259570
136 13660967
137 14071412
138 14491040
139 14919987
140 15358390
141 15806387
142 16264117
143 16731720
144 17209337
145 17697110
146 18195182
147 18703697
148 19222800
149 19752637
150 20293355
151 20845102
152 21408027
153 21982280
154 22568012
155 23165375
156 23774522
157 24395607
158 25028785
159 25674212
160 26332045
161 27002442
162 27685562
163 28381565
164 29090612
165 29812865
166 30548487
167 31297642
168 32060495
169 32837212
170 33627960
171 34432907
172 35252222
173 36086075
174 36934637
175 37798080
176 38676577
177 39570302
178 40479430
179 41404137
180 42344600
181 43300997
182 44273507
183 45262310
184 46267587
185 47289520
186 48328292
187 49384087
188 50457090
189 51547487
190 52655465
191 53781212
192 54924917
193 56086770
194 57266962
195 58465685
196 59683132
197 60919497
198 62174975
199 63449762
200 64744055
201 66058052
202 67391952
203 68745955
204 70120262
205 71515075
206 72930597
207 74367032
208 75824585
209 77303462
210 78803870
211 80326017
212 81870112
213 83436365
214 85024987
215 86636190
216 88270187
217 89927192
218 91607420
219 93311087
220 95038410
221 96789607
222 98564897
223 100364500
224 102188637
225 104037530
226 105911402
227 107810477
228 109734980
229 111685137
230 113661175
231 115663322
232 117691807
233 119746860
234 121828712
235 123937595
236 126073742
237 128237387
238 130428765
239 132648112
240 134895665
241 137171662
242 139476342
243 141809945
244 144172712
245 146564885
246 148986707
247 151438422
248 153920275
249 156432512
250 158975380
251 161549127
252 164154002
253 166790255
254 169458137
255 172157900
256 174889797
257 177654082
258 180451010
259 183280837
260 186143820
261 189040217
262 191970287
263 194934290
264 197932487
265 200965140
266 204032512
267 207134867
268 210272470
269 213445587
270 216654485
271 219899432
272 223180697
273 226498550
274 229853262
275 233245105
276 236674352
277 240141277
278 243646155
279 247189262
280 250770875
281 254391272
282 258050732
283 261749535
284 265487962
285 269266295
286 273084817
287 276943812
288 280843565
289 284784362
290 288766490
291 292790237
292 296855892
293 300963745
294 305114087
295 309307210
296 313543407
297 317822972
298 322146200
299 326513387
300 330924830
301 335380827
302 339881677
303 344427680
304 349019137
305 353656350
306 358339622
307 363069257
308 367845560
309 372668837
310 377539395
311 382457542
312 387423587
313 392437840
314 397500612
315 402612215
316 407772962
317 412983167
318 418243145
319 423553212
320 428913685
321 434324882
322 439787122
323 445300725
324 450866012
325 456483305
326 462152927
327 467875202
328 473650455
329 479479012
330 485361200
331 491297347
332 497287782
333 503332835
334 509432837
335 515588120
336 521799017
337 528065862
338 534388990
339 540768737
340 547205440
341 553699437
342 560251067
343 566860670
344 573528587
345 580255160
346 587040732
347 593885647
348 600790250
349 607754887
350 614779905
351 621865652
352 629012477
353 636220730
354 643490762
355 650822925
356 658217572
357 665675057
358 673195735
359 680779962
360 688428095
361 696140492
362 703917512
363 711759515
364 719666862
365 727639915
366 735679037
367 743784592
368 751956945
369 760196462
370 768503510
371 776878457
372 785321672
373 793833525
374 802414387
375 811064630
376 819784627
377 828574752
378 837435380
379 846366887
380 855369650
381 864444047
382 873590457
383 882809260
384 892100837
385 901465570
386 910903842
387 920416037
388 930002540
389 939663737
390 949400015
391 959211762
392 969099367
393 979063220
394 989103712
395 999221235
396 1009416182
397 1019688947
398 1030039925
399 1040469512
400 1050978105
401 1061566102
402 1072233902
403 1082981905
404 1093810512
405 1104720125
406 1115711147
407 1126783982
408 1137939035
409 1149176712
410 1160497420
411 1171901567
412 1183389562
413 1194961815
414 1206618737
415 1218360740
416 1230188237
417 1242101642
418 1254101370
419 1266187837
420 1278361460
421 1290622657
422 1302971847
423 1315409450
424 1327935887
425 1340551580
426 1353256952
427 1366052427
428 1378938430
429 1391915387
430 1404983725
431 1418143872
432 1431396257
433 1444741310
434 1458179462
435 1471711145
436 1485336792
437 1499056837
438 1512871715
439 1526781862
440 1540787715
441 1554889712
442 1569088292
443 1583383895
444 1597776962
445 1612267935
446 1626857257
447 1641545372
448 1656332725
449 1671219762
450 1686206930
451 1701294677
452 1716483452
453 1731773705
454 1747165887
455 1762660450
456 1778257847
457 1793958532
458 1809762960
459 1825671587
460 1841684870
461 1857803267
462 1874027237
463 1890357240
464 1906793737
465 1923337190
466 1939988062
467 1956746817
468 1973613920
469 1990589837
470 2007675035
471 2024869982
472 2042175147
473 2059591000
474 2077118012
475 2094756655
476 2112507402
477 2130370727
478 2148347105
479 2166437012
480 2184640925
481 2202959322
482 2221392682
483 2239941485
484 2258606212
485 2277387345
486 2296285367
487 2315300762
488 2334434015
489 2353685612
490 2373056040
491 2392545787
492 2412155342
493 2431885195
494 2451735837
495 2471707760
496 2491801457
497 2512017422
498 2532356150
499 2552818137
500 2573403880
501 2594113877
502 2614948627
503 2635908630
504 2656994387
505 2678206400
506 2699545172
507 2721011207
508 2742605010
509 2764327087
510 2786177945
511 2808158092
512 2830268037
513 2852508290
514 2874879362
515 2897381765
516 2920016012
517 2942782617
518 2965682095
519 2988714962
520 3011881735
521 3035182932
522 3058619072
523 3082190675
524 3105898262
525 3129742355
526 3153723477
527 3177842152
528 3202098905
529 3226494262
530 3251028750
531 3275702897
532 3300517232
533 3325472285
534 3350568587
535 3375806670
536 3401187067
537 3426710312
538 3452376940
539 3478187487
540 3504142490
541 3530242487
542 3556488017
543 3582879620
544 3609417837
545 3636103210
546 3662936282
547 3689917597
548 3717047700
549 3744327137
550 3771756455
551 3799336202
552 3827066927
553 3854949180
554 3882983512
555 3911170475
556 3939510622
557 3968004507
558 3996652685
559 4025455712
560 4054414145
561 4083528542
562 4112799462
563 4142227465
564 4171813112
565 4201556965
566 4231459587
567 4261521542
568 4291743395
569 4322125712
570 4352669060
571 4383374007
572 4414241122
573 4445270975
574 4476464137
575 4507821180
576 4539342677
577 4571029202
578 4602881330
579 4634899637
580 4667084700
581 4699437097
582 4731957407
583 4764646210
584 4797504087
585 4830531620
586 4863729392
587 4897097987
588 4930637990
589 4964349987
590 4998234565
591 5032292312
592 5066523817
593 5100929670
594 5135510462
595 5170266785
596 5205199232
597 5240308397
598 5275594875
599 5311059262
600 5346702155
601 5382524152
602 5418525852
603 5454707855
604 5491070762
605 5527615175
606 5564341697
607 5601250932
608 5638343485
609 5675619962
610 5713080970
611 5750727117
612 5788559012
613 5826577265
614 5864782487
615 5903175290
616 5941756287
617 5980526092
618 6019485320
619 6058634587
620 6097974510
621 6137505707
622 6177228797
623 6217144400
624 6257253137
625 6297555630
626 6338052502
627 6378744377
628 6419631880
629 6460715637
630 6501996275
631 6543474422
632 6585150707
633 6627025760
634 6669100212
635 6711374695
636 6753849842
637 6796526287
638 6839404665
639 6882485612
640 6925769765
641 6969257762
642 7012950242
643 7056847845
644 7100951212
645 7145260985
646 7189777807
647 7234502322
648 7279435175
649 7324577012
650 7369928480
651 7415490227
652 7461262902
653 7507247155
654 7553443637
655 7599853000
656 7646475897
657 7693312982
658 7740364910
659 7787632337
660 7835115920
661 7882816317
662 7930734187
663 7978870190
664 8027224987
665 8075799240
666 8124593612
667 8173608767
668 8222845370
669 8272304087
670 8321985585
671 8371890532
672 8422019597
673 8472373450
674 8522952762
675 8573758205
676 8624790452
677 8676050177
678 8727538055
679 8779254762
680 8831200975
681 8883377372
682 8935784632
683 8988423435
684 9041294462
685 9094398395
686 9147735917
687 9201307712
688 9255114465
689 9309156862
690 9363435590
691 9417951337
692 9472704792
693 9527696645
694 9582927587
695 9638398310
696 9694109507
697 9750061872
698 9806256100
699 9862692887
700 9919372930
701 9976296927
702 10033465577
703 10090879580
704 10148539637
705 10206446450
706 10264600722
707 10323003157
708 10381654460
709 10440555337
710 10499706495
711 10559108642
712 10618762487
713 10678668740
714 10738828112
715 10799241315
716 10859909062
717 10920832067
718 10982011045
719 11043446712
720 11105139785
721 11167090982
722 11229301022
723 11291770625
724 11354500512
725 11417491405
726 11480744027
727 11544259102
728 11608037355
729 11672079512
730 11736386300
731 11800958447
732 11865796682
733 11930901735
734 11996274337
735 12061915220
736 12127825117
737 12194004762
738 12260454890
739 12327176237
740 12394169540
741 12461435537
742 12528974967
743 12596788570
744 12664877087
745 12733241260
746 12801881832
747 12870799547
748 12939995150
749 13009469387
750 13079223005
751 13149256752
752 13219571377
753 13290167630
754 13361046262
755 13432208025
756 13503653672
757 13575383957
758 13647399635
759 13719701462
760 13792290195
761 13865166592
762 13938331412
763 14011785415
764 14085529362
765 14159564015
766 14233890137
767 14308508492
768 14383419845
769 14458624962
770 14534124610
771 14609919557
772 14686010572
773 14762398425
774 14839083887
775 14916067730
776 14993350727
777 15070933652
778 15148817280
779 15227002387
780 15305489750
781 15384280147
782 15463374357
783 15542773160
784 15622477337
785 15702487670
786 15782804942
787 15863429937
788 15944363440
789 16025606237
790 16107159115
791 16189022862
792 16271198267
793 16353686120
794 16436487212
795 16519602335
796 16603032282
797 16686777847
798 16770839825
799 16855219012
800 16939916205
801 17024932202
802 17110267802
803 17195923805
804 17281901012
805 17368200225
806 17454822247
807 17541767882
808 17629037935
809 17716633212
810 17804554520
811 17892802667
812 17981378462
813 18070282715
814 18159516237
815 18249079840
816 18338974337
817 18429200542
818 18519759270
819 18610651337
820 18701877560
821 18793438757
822 18885335747
823 18977569350
824 19070140387
825 19163049680
826 19256298052
827 19349886327
828 19443815330
829 19538085887
830 19632698825
831 19727654972
832 19822955157
833 19918600210
834 20014590962
835 20110928245
836 20207612892
837 20304645737
838 20402027615
839 20499759362
840 20597841815
841 20696275812
842 20795062192
843 20894201795
844 20993695462
845 21093544035
846 21193748357
847 21294309272
848 21395227625
849 21496504262
850 21598140030
851 21700135777
852 21802492352
853 21905210605
854 22008291387
855 22111735550
856 22215543947
857 22319717432
858 22424256860
859 22529163087
860 22634436970
861 22740079367
862 22846091137
863 22952473140
864 23059226237
865 23166351290
866 23273849162
867 23381720717
868 23489966820
869 23598588337
870 23707586135
871 23816961082
872 23926714047
873 24036845900
874 24147357512
875 24258249755
876 24369523502
877 24481179627
878 24593219005
879 24705642512
880 24818451025
881 24931645422
882 25045226582
883 25159195385
884 25273552712
885 25388299445
886 25503436467
887 25618964662
888 25734884915
889 25851198112
890 25967905140
891 26085006887
892 26202504242
893 26320398095
894 26438689337
895 26557378860
896 26676467557
897 26795956322
898 26915846050
899 27036137637
900 27156831980
901 27277929977
902 27399432527
903 27521340530
904 27643654887
905 27766376500
906 27889506272
907 28013045107
908 28136993910
909 28261353587
910 28386125045
911 28511309192
912 28636906937
913 28762919190
914 28889346862
915 29016190865
916 29143452112
917 29271131517
918 29399229995
919 29527748462
920 29656687835
921 29786049032
922 29915832972
923 30046040575
924 30176672762
925 30307730455
926 30439214577
927 30571126052
928 30703465805
929 30836234762
930 30969433850
931 31103063997
932 31237126132
933 31371621185
934 31506550087
935 31641913770
936 31777713167
937 31913949212
938 32050622840
939 32187734987
940 32325286590
941 32463278587
942 32601711917
943 32740587520
944 32879906337
945 33019669310
946 33159877382
947 33300531497
948 33441632600
949 33583181637
950 33725179555
951 33867627302
952 34010525827
953 34153876080
954 34297679012
955 34441935575
956 34586646722
957 34731813407
958 34877436585
959 35023517212
960 35170056245
961 35317054642
962 35464513362
963 35612433365
964 35760815612
965 35909661065
966 36058970687
967 36208745442
968 36358986295
969 36509694212
970 36660870160
971 36812515107
972 36964630022
973 37117215875
974 37270273637
975 37423804280
976 37577808777
977 37732288102
978 37887243230
979 38042675137
980 38198584800
981 38354973197
982 38511841307
983 38669190110
984 38827020587
985 38985333720
986 39144130492
987 39303411887
988 39463178890
989 39623432487
990 39784173665
991 39945403412
992 40107122717
993 40269332570
994 40432033962
995 40595227885
996 40758915332
997 40923097297
998 41087774775
999 41252948762
1000 41418620255