1 0
2 12673
3 41788
4 47656
5 82348
6 85485
7 95325
8 109020
9 144313
10 165385
11 171465
12 207417
13 215373
14 227268
15 251781
16 258013
17 271660
18 303025
19 316848
20 357717
21 396340
22 407092
23 410533
24 436356
25 464145
26 490360
27 503217
28 529720
29 533281
30 544453
31 585156
32 600117
33 603748
34 644368
35 649681
36 694540
37 701592
38 729585
39 752556
40 768217
41 796720
42 802108
43 870573
44 887568
45 899868
46 903805
47 955405
48 961180
49 965181
50 1009953
51 1026720
52 1065285
53 1073065
54 1090108
55 1121133
56 1136356
57 1146600
58 1201560
59 1229656
60 1237768
61 1296420
62 1314453
63 1353492
64 1364308
65 1371781
66 1413856
67 1432417
68 1440945
69 1502613
70 1541605
71 1553853
72 1558492
73 1593325
74 1630848
75 1645656
76 1666281
77 1685992
78 1739500
79 1751356
80 1794685
81 1814988
82 1819917
83 1835385
84 1882320
85 1891792
86 1952953
87 1991088
88 2022405
89 2043768
90 2082673
91 2092573
92 2124592
93 2164185
94 2183620
95 2223717
96 2229108
97 2307733
98 2313220
99 2330440
100 2335953
101 2397681
102 2461368
103 2484805
104 2527492
105 2562553
106 2573493
107 2616948
108 2638281
109 2688217
110 2769181
111 2794092
112 2805540
113 2863005
114 2873340
115 2882217
116 2888368
117 2957248
118 2969056
119 3054492
120 3080781
121 3108556
122 3128668
123 3232417
124 3252985
125 3281640
126 3309033
127 3399925
128 3412717
129 3488485
130 3495348
131 3505281
132 3516888
133 3582273
134 3595473
135 3624400
136 3720388
137 3781140
138 3807465
139 3861792
140 3875620
141 3920353
142 3975688
143 4006485
144 4091700
145 4176492
146 4184173
147 4208281
148 4216000
149 4328625
150 4336488
151 4395553
152 4424556
153 4484413
154 4533592
155 4548940
156 4609917
157 4643856
158 4694205
159 4756492
160 4858693
161 4874781
162 4955556
163 4982568
164 4991217
165 5027056
166 5104705
167 5126233
168 5224933
169 5261940
170 5301045
171 5329365
172 5402056
173 5470753
174 5479992
175 5504488
176 5583480
177 5711628
178 5729668
179 5769205
180 5860240
181 5876617
182 5900433
183 5987520
184 6028353
185 6163885
186 6182965
187 6249693
188 6383181
189 6408505
190 6446400
191 6524617
192 6568156
193 6588168
194 6688653
195 6733020
196 6853560
197 6864481
198 6880288
199 7023856
200 7034985
201 7069917
202 7118592
203 7319617
204 7335781
205 7422148
206 7470225
207 7541556
208 7629813
209 7652281
210 7797460
211 7814917
212 7950265
213 7962528
214 8013345
215 8153992
216 8193220
217 8205781
218 8300148
219 8346493
220 8442156
221 8545305
222 8642800
223 8655913
224 8697073
225 8847288
226 9010365
227 9066508
228 9195793
229 9252880
230 9279120
231 9383385
232 9434592
233 9469068
234 9627156
235 9654268
236 9749092
237 9910953
238 9974808
239 10021056
240 10035865
241 10201765
242 10230217
243 10373092
244 10436181
245 10499592
246 10645617
247 10675105
248 10849825
249 10865656
250 10915348
251 10984593
252 11163492
253 11270608
254 11301556
255 11484928
256 11525592
257 11586445
258 11712060
259 11744040
260 11814133
261 11975548
262 12046825
263 12258048
264 12458313
265 12514173
266 12532060
267 12666445
268 12811356
269 12948333
270 13015608
271 13154481
272 13173160
273 13231792
274 13445785
275 13524588
276 13543725
277 13758117
278 13786200
279 14023681
280 14061073
281 14209656
282 14331765
283 14415108
284 14566981
285 14595717
286 14961592
287 15052617
288 15118545
289 15139656
290 15416728
291 15447781
292 15469300
293 15710380
294 15800793
295 16009008
296 16051056
297 16143217
298 16311160
299 16393645
300 16449181
301 16747533
302 16900305
303 16944445
304 17263993
305 17362380
306 17575593
307 17634717
308 17675580
309 17905845
310 18007528
311 18054268
312 18392640
313 18606928
314 18674292
315 18699813
316 18891556
317 19098325
318 19179985
319 19293780
320 19402593
321 19698273
322 19763845
323 20003656
324 20116117
325 20143428
326 20229156
327 20489481
328 20542053
329 20881792
330 21093865
331 21268156
332 21387117
333 21603900
334 21659092
335 21837673
336 22058656
337 22167193
338 22391248
339 22421385
340 22861260
341 22891981
342 22988413
343 23019292
344 23365240
345 23722545
346 23854128
347 24093913
348 24290980
349 24352492
350 24596925
351 24716980
352 24998148
353 25454440
354 25594933
355 25659513
356 25983828
357 26042181
358 26092308
359 26127045
360 26516217
361 26582965
362 27066193
363 27214980
364 27372225
365 27486117
366 28074028
367 28190656
368 28353181
369 28508592
370 29024556
371 29097208
372 29527708
373 29566717
374 29623180
375 29689165
376 30061000
377 30136092
378 30300681
379 30847117
380 31193181
381 31343188
382 31652853
383 31731693
384 31986792
385 32302465
386 32478208
387 32964681
388 33449013
389 33492900
390 33630660
391 33674773
392 34318648
393 34363617
394 34701480
395 34867425
396 35209992
397 35491533
398 35579413
399 35928628
400 36123045
401 36411528
402 36768513
403 37354492
404 37446760
405 37910125
406 38065117
407 38114748
408 38320425
409 38766156
410 38889760
411 39456592
412 39669181
413 39893856
414 40056588
415 40474365
416 40869292
417 40922413
418 41063265
419 41517553
420 42254805
421 42358617
422 42586156
423 43110181
424 43204468
425 43341592
426 43843093
427 44078280
428 44859108
429 44969056
430 45353620
431 46123140
432 46269156
433 46487673
434 46938768
435 47189905
436 47305345
437 47885080
438 48141093
439 48836781
440 48899820
441 48991065
442 49819945
443 49884208
444 50085928
445 50367033
446 51528268
447 51621660
448 52120717
449 52398556
450 52810825
451 53320992
452 53450880
453 54290281
454 54391228
455 55173988
456 55244917
457 55538856
458 56352513
459 56579481
460 56652160
461 57198217
462 57466420
463 58020085
464 58617156
465 59181573
466 59257492
467 59495800
468 60365617
469 61310088
470 61635285
471 62384220
472 62714953
473 62866981
474 63471108
475 63767833
476 63967617
477 64883805
478 65040945
479 65590573
480 66528880
481 66899085
482 67167225
483 67253088
484 68215056
485 68380048
486 69208633
487 69574540
488 69942333
489 70789368
490 70960428
491 71974056
492 72065905
493 72354217
494 72755992
495 73794093
496 74415717
497 74595325
498 75659605
499 75895633
500 76248856
501 76978033
502 77163681
503 77570592
504 78507717
505 78921556
506 80148025
507 81310992
508 81635400
509 81739281
510 82519768
511 83361445
512 84157092
513 84547885
514 85354620
515 85463133
516 85803753
517 87047008
518 87504865
519 87616056
520 88861788
521 89024973
522 90405000
523 90622300
524 91485805
525 92195488
526 92679885
527 93562620
528 93729648
529 95856433
530 96385588
531 96768856
532 96891585
533 98502417
534 98682960
535 98808073
536 100209781
537 100735492
538 101946217
539 102190725
540 102726648
541 103703281
542 104182968
543 104505940
544 106241092
545 107129628
546 107386356
547 109244992
548 109817281
549 111057520
550 111401448
551 111639153
552 112978668
553 113570205
554 113842117
555 115810681
556 117057417
557 117449353
558 117597840
559 118713465
560 119916556
561 120391708
562 121053853
563 121687020
564 123407592
565 123789168
566 125184705
567 125839168
568 125998105
569 126497005
570 128012020
571 128317980
572 130295253
573 131529556
574 132543985
575 133236388
576 134498181
577 134819433
578 135858900
579 137145205
580 137776992
581 139081225
582 139256656
583 141817281
584 141996120
585 142557492
586 142737253
587 144751213
588 146831356
589 147597417
590 148993440
591 150140781
592 150498913
593 151922056
594 152621053
595 154258125
596 156914913
597 157732960
598 158108992
599 159997417
600 160337200
601 160629085
602 160831356
603 163097508
604 163486188
605 166300120
606 167166553
607 168082248
608 168745488
609 172169205
610 172848405
611 173794900
612 174699973
613 177704865
614 178127985
615 180635217
616 180862408
617 181191253
618 181575556
619 183741181
620 184178533
621 185137140
622 188319768
623 190335400
624 191209117
625 193012780
626 193471992
627 194957853
628 196796556
629 197820217
630 200653840
631 203475040
632 203730681
633 204533133
634 204790092
635 208540717
636 208802668
637 210770781
638 211737448
639 213732993
640 215373060
641 215884992
642 217919305
643 219051868
644 220732417
645 222812040
646 226225713
647 226763233
648 229462648
649 230365588
650 230654725
651 231852948
652 234449685
653 235169781
654 238472073
655 239710600
656 241019545
657 241967617
658 244401588
659 246702453
660 247011940
661 247832556
662 250479292
663 254774656
664 255379488
665 256705185
666 259758300
667 260307645
668 261106573
669 264028492
670 265398781
671 269948217
672 270588825
673 272829481
674 277313113
675 278163885
676 279437092
677 282065445
678 283528728
679 284201356
680 287579281
681 289070992
682 293124580
683 293491893
684 294023556
685 298853268
686 299227717
687 300403105
688 302041060
689 308807445
690 309351633
691 312259608
692 313878565
693 316280848
694 319253593
695 320010453
696 324901680
697 325489905
698 330051117
699 330464428
700 332177245
701 336918540
702 338241120
703 338664633
704 341846608
705 343409481
706 346635808
707 350115085
708 353404092
709 353846493
710 355235181
711 360303868
712 365807617
713 367702656
714 372066981
715 373994292
716 374880220
717 378400717
718 380129860
719 381294088
720 386633128
721 387548856
722 390751800
723 396219781
724 398377156
725 399939748
726 400440117
727 406046025
728 407007525
729 411836160
730 413968513
731 416111860
732 421048045
733 422044917
734 427951965
735 428487228
736 430167408
737 432508813
738 438558520
739 442181148
740 443227848
741 449430156
742 450805660
743 452864145
744 457113592
745 458195500
746 460566873
747 466028208
748 468439965
749 475587556
750 482365093
751 484255681
752 484861080
753 489409617
754 494314768
755 498951673
756 501229156
757 505930693
758 506563092
759 508548180
760 515793717
761 518462056
762 519110065
763 526370065
764 527321092
765 535363773
766 536630181
767 541662628
768 545798617
769 548621656
770 553766193
771 554739625
772 567134460
773 570218365
774 572452045
775 573167308
776 582555228
777 583607433
778 584336592
779 592505760
780 595569613
781 602625748
782 604050748
783 607174125
784 612865980
785 615661617
786 617543913
787 627656473
788 632834917
789 634331145
790 645163413
791 648498760
792 655726981
793 657731425
794 659116792
795 666923617
796 670371156
797 671955888
798 683428900
799 690695028
800 692979280
801 693844681
802 700346688
803 707358465
804 710127717
805 713986792
806 717676981
807 727704733
808 729928617
809 738062028
810 741876345
811 742802656
812 745710328
813 754540093
814 756323281
815 767847180
816 775040925
817 780953208
818 784988665
819 792342640
820 794214960
821 800273181
822 807770028
823 811452213
824 819053556
825 820076005
826 834999880
827 836042193
828 839313993
829 840361680
830 852099492
831 864223045
832 868687828
833 876824181
834 883511160
835 885598440
836 893892865
837 897966792
838 907508056
839 922992492
840 927760281
841 929951893
842 940958128
843 942938473
844 944639656
845 945818545
846 959026285
847 961291617
848 977691981
849 982741792
850 988078717
851 991944265
852 1011898656
853 1015857228
854 1021373673
855 1026648700
856 1044162088
857 1046628156
858 1061241048
859 1062565185
860 1064481792
861 1066721625
862 1079343540
863 1081892560
864 1087479613
865 1106028945
866 1117776673
867 1122868968
868 1133381281
869 1136057713
870 1144717780
871 1155434325
872 1161400548
873 1177915813
874 1194358681
875 1195848640
876 1200525592
877 1202023233
878 1223883108
879 1225409845
880 1236880660
881 1242514717
882 1254145420
883 1263704281
884 1266687993
885 1278544656
886 1285145617
887 1294940428
888 1307061181
889 1326957240
890 1330090092
891 1345823217
892 1351085865
893 1352771056
894 1359754717
895 1374889408
896 1379086380
897 1398333300
898 1405551873
899 1413180868
900 1418706568
901 1432892617
902 1446302880
903 1448106681
904 1452889525
905 1468315653
906 1493350585
907 1496875765
908 1504602408
909 1522397073
910 1525598856
911 1530255300
912 1547285313
913 1555271860
914 1581787648
915 1585521348
916 1598580720
917 1624712992
918 1629671608
919 1637092333
920 1652411356
921 1660939917
922 1664860245
923 1684548060
924 1693242313
925 1716868153
926 1719008992
927 1722107725
928 1750257117
929 1752439548
930 1759290156
931 1768836781
932 1808273856
933 1811445592
934 1828394385
935 1837830288
936 1851831717
937 1869158020
938 1873569292
939 1902077253
940 1905505656
941 1932090168
942 1934499105
943 1944482068
944 1972116181
945 1979824693
946 1982293092
947 2000838885
948 2009947920
949 2028752217
950 2049030808
951 2068200433
952 2070778920
953 2078872740
954 2108415045
955 2140493068
956 2151538105
957 2176975120
958 2188208253
959 2193371793
960 2213890648
961 2223968781
962 2230754365
963 2261872417
964 2267209645
965 2285877681
966 2317747260
967 2330321305
968 2339428717
969 2342345068
970 2375018548
971 2380622556
972 2408765781
973 2421193992
974 2433686281
975 2462456356
976 2468266528
977 2502695188
978 2505814917
979 2515607685
980 2529254340
981 2564514481
982 2585628625
983 2591729217
984 2627878785
985 2635895781
986 2647893468
987 2672660973
988 2678966773
989 2692788100
990 2724618985
991 2738675688
992 2780334765
993 2819837020
994 2830856140
995 2834384653
996 2860895388
997 2889484617
998 2916510400
999 2929784505
1000 2957186992