1 1
2 16
3 70
4 189
5 399
6 726
7 1196
8 1835
9 2669
10 3724
11 5026
12 6601
13 8475
14 10674
15 13224
16 16151
17 19481
18 23240
19 27454
20 32149
21 37351
22 43086
23 49380
24 56259
25 63749
26 71876
27 80666
28 90145
29 100339
30 111274
31 122976
32 135471
33 148785
34 162944
35 177974
36 193901
37 210751
38 228550
39 247324
40 267099
41 287901
42 309756
43 332690
44 356729
45 381899
46 408226
47 435736
48 464455
49 494409
50 525624
51 558126
52 591941
53 627095
54 663614
55 701524
56 740851
57 781621
58 823860
59 867594
60 912849
61 959651
62 1008026
63 1058000
64 1109599
65 1162849
66 1217776
67 1274406
68 1332765
69 1392879
70 1454774
71 1518476
72 1584011
73 1651405
74 1720684
75 1791874
76 1865001
77 1940091
78 2017170
79 2096264
80 2177399
81 2260601
82 2345896
83 2433310
84 2522869
85 2614599
86 2708526
87 2804676
88 2903075
89 3003749
90 3106724
91 3212026
92 3319681
93 3429715
94 3542154
95 3657024
96 3774351
97 3894161
98 4016480
99 4141334
100 4268749
101 4398751
102 4531366
103 4666620
104 4804539
105 4945149
106 5088476
107 5234546
108 5383385
109 5535019
110 5689474
111 5846776
112 6006951
113 6170025
114 6336024
115 6504974
116 6676901
117 6851831
118 7029790
119 7210804
120 7394899
121 7582101
122 7772436
123 7965930
124 8162609
125 8362499
126 8565626
127 8772016
128 8981695
129 9194689
130 9411024
131 9630726
132 9853821
133 10080335
134 10310294
135 10543724
136 10780651
137 11021101
138 11265100
139 11512674
140 11763849
141 12018651
142 12277106
143 12539240
144 12805079
145 13074649
146 13347976
147 13625086
148 13906005
149 14190759
150 14479374
151 14771876
152 15068291
153 15368645
154 15672964
155 15981274
156 16293601
157 16609971
158 16930410
159 17254944
160 17583599
161 17916401
162 18253376
163 18594550
164 18939949
165 19289599
166 19643526
167 20001756
168 20364315
169 20731229
170 21102524
171 21478226
172 21858361
173 22242955
174 22632034
175 23025624
176 23423751
177 23826441
178 24233720
179 24645614
180 25062149
181 25483351
182 25909246
183 26339860
184 26775219
185 27215349
186 27660276
187 28110026
188 28564625
189 29024099
190 29488474
191 29957776
192 30432031
193 30911265
194 31395504
195 31884774
196 32379101
197 32878511
198 33383030
199 33892684
200 34407499
201 34927501
202 35452716
203 35983170
204 36518889
205 37059899
206 37606226
207 38157896
208 38714935
209 39277369
210 39845224
211 40418526
212 40997301
213 41581575
214 42171374
215 42766724
216 43367651
217 43974181
218 44586340
219 45204154
220 45827649
221 46456851
222 47091786
223 47732480
224 48378959
225 49031249
226 49689376
227 50353366
228 51023245
229 51699039
230 52380774
231 53068476
232 53762171
233 54461885
234 55167644
235 55879474
236 56597401
237 57321451
238 58051650
239 58788024
240 59530599
241 60279401
242 61034456
243 61795790
244 62563429
245 63337399
246 64117726
247 64904436
248 65697555
249 66497109
250 67303124
251 68115626
252 68934641
253 69760195
254 70592314
255 71431024
256 72276351
257 73128321
258 73986960
259 74852294
260 75724349
261 76603151
262 77488726
263 78381100
264 79280299
265 80186349
266 81099276
267 82019106
268 82945865
269 83879579
270 84820274
271 85767976
272 86722711
273 87684505
274 88653384
275 89629374
276 90612501
277 91602791
278 92600270
279 93604964
280 94616899
281 95636101
282 96662596
283 97696410
284 98737569
285 99786099
286 100842026
287 101905376
288 102976175
289 104054449
290 105140224
291 106233526
292 107334381
293 108442815
294 109558854
295 110682524
296 111813851
297 112952861
298 114099580
299 115254034
300 116416249
301 117586251
302 118764066
303 119949720
304 121143239
305 122344649
306 123553976
307 124771246
308 125996485
309 127229719
310 128470974
311 129720276
312 130977651
313 132243125
314 133516724
315 134798474
316 136088401
317 137386531
318 138692890
319 140007504
320 141330399
321 142661601
322 144001136
323 145349030
324 146705309
325 148069999
326 149443126
327 150824716
328 152214795
329 153613389
330 155020524
331 156436226
332 157860521
333 159293435
334 160734994
335 162185224
336 163644151
337 165111801
338 166588200
339 168073374
340 169567349
341 171070151
342 172581806
343 174102340
344 175631779
345 177170149
346 178717476
347 180273786
348 181839105
349 183413459
350 184996874
351 186589376
352 188190991
353 189801745
354 191421664
355 193050774
356 194689101
357 196336671
358 197993510
359 199659644
360 201335099
361 203019901
362 204714076
363 206417650
364 208130649
365 209853099
366 211585026
367 213326456
368 215077415
369 216837929
370 218608024
371 220387726
372 222177061
373 223976055
374 225784734
375 227603124
376 229431251
377 231269141
378 233116820
379 234974314
380 236841649
381 238718851
382 240605946
383 242502960
384 244409919
385 246326849
386 248253776
387 250190726
388 252137725
389 254094799
390 256061974
391 258039276
392 260026731
393 262024365
394 264032204
395 266050274
396 268078601
397 270117211
398 272166130
399 274225384
400 276294999
401 278375001
402 280465416
403 282566270
404 284677589
405 286799399
406 288931726
407 291074596
408 293228035
409 295392069
410 297566724
411 299752026
412 301948001
413 304154675
414 306372074
415 308600224
416 310839151
417 313088881
418 315349440
419 317620854
420 319903149
421 322196351
422 324500486
423 326815580
424 329141659
425 331478749
426 333826876
427 336186066
428 338556345
429 340937739
430 343330274
431 345733976
432 348148871
433 350574985
434 353012344
435 355460974
436 357920901
437 360392151
438 362874750
439 365368724
440 367874099
441 370390901
442 372919156
443 375458890
444 378010129
445 380572899
446 383147226
447 385733136
448 388330655
449 390939809
450 393560624
451 396193126
452 398837341
453 401493295
454 404161014
455 406840524
456 409531851
457 412235021
458 414950060
459 417676994
460 420415849
461 423166651
462 425929426
463 428704200
464 431490999
465 434289849
466 437100776
467 439923806
468 442758965
469 445606279
470 448465774
471 451337476
472 454221411
473 457117605
474 460026084
475 462946874
476 465880001
477 468825491
478 471783370
479 474753664
480 477736399
481 480731601
482 483739296
483 486759510
484 489792269
485 492837599
486 495895526
487 498966076
488 502049275
489 505145149
490 508253724
491 511375026
492 514509081
493 517655915
494 520815554
495 523988024
496 527173351
497 530371561
498 533582680
499 536806734
500 540043749
501 543293751
502 546556766
503 549832820
504 553121939
505 556424149
506 559739476
507 563067946
508 566409585
509 569764419
510 573132474
511 576513776
512 579908351
513 583316225
514 586737424
515 590171974
516 593619901
517 597081231
518 600555990
519 604044204
520 607545899
521 611061101
522 614589836
523 618132130
524 621688009
525 625257499
526 628840626
527 632437416
528 636047895
529 639672089
530 643310024
531 646961726
532 650627221
533 654306535
534 657999694
535 661706724
536 665427651
537 669162501
538 672911300
539 676674074
540 680450849
541 684241651
542 688046506
543 691865440
544 695698479
545 699545649
546 703406976
547 707282486
548 711172205
549 715076159
550 718994374
551 722926876
552 726873691
553 730834845
554 734810364
555 738800274
556 742804601
557 746823371
558 750856610
559 754904344
560 758966599
561 763043401
562 767134776
563 771240750
564 775361349
565 779496599
566 783646526
567 787811156
568 791990515
569 796184629
570 800393524
571 804617226
572 808855761
573 813109155
574 817377434
575 821660624
576 825958751
577 830271841
578 834599920
579 838943014
580 843301149
581 847674351
582 852062646
583 856466060
584 860884619
585 865318349
586 869767276
587 874231426
588 878710825
589 883205499
590 887715474
591 892240776
592 896781431
593 901337465
594 905908904
595 910495774
596 915098101
597 919715911
598 924349230
599 928998084
600 933662499
601 938342501
602 943038116
603 947749370
604 952476289
605 957218899
606 961977226
607 966751296
608 971541135
609 976346769
610 981168224
611 986005526
612 990858701
613 995727775
614 1000612774
615 1005513724
616 1010430651
617 1015363581
618 1020312540
619 1025277554
620 1030258649
621 1035255851
622 1040269186
623 1045298680
624 1050344359
625 1055406249
626 1060484376
627 1065578766
628 1070689445
629 1075816439
630 1080959774
631 1086119476
632 1091295571
633 1096488085
634 1101697044
635 1106922474
636 1112164401
637 1117422851
638 1122697850
639 1127989424
640 1133297599
641 1138622401
642 1143963856
643 1149321990
644 1154696829
645 1160088399
646 1165496726
647 1170921836
648 1176363755
649 1181822509
650 1187298124
651 1192790626
652 1198300041
653 1203826395
654 1209369714
655 1214930024
656 1220507351
657 1226101721
658 1231713160
659 1237341694
660 1242987349
661 1248650151
662 1254330126
663 1260027300
664 1265741699
665 1271473349
666 1277222276
667 1282988506
668 1288772065
669 1294572979
670 1300391274
671 1306226976
672 1312080111
673 1317950705
674 1323838784
675 1329744374
676 1335667501
677 1341608191
678 1347566470
679 1353542364
680 1359535899
681 1365547101
682 1371575996
683 1377622610
684 1383686969
685 1389769099
686 1395869026
687 1401986776
688 1408122375
689 1414275849
690 1420447224
691 1426636526
692 1432843781
693 1439069015
694 1445312254
695 1451573524
696 1457852851
697 1464150261
698 1470465780
699 1476799434
700 1483151249
701 1489521251
702 1495909466
703 1502315920
704 1508740639
705 1515183649
706 1521644976
707 1528124646
708 1534622685
709 1541139119
710 1547673974
711 1554227276
712 1560799051
713 1567389325
714 1573998124
715 1580625474
716 1587271401
717 1593935931
718 1600619090
719 1607320904
720 1614041399
721 1620780601
722 1627538536
723 1634315230
724 1641110709
725 1647924999
726 1654758126
727 1661610116
728 1668480995
729 1675370789
730 1682279524
731 1689207226
732 1696153921
733 1703119635
734 1710104394
735 1717108224
736 1724131151
737 1731173201
738 1738234400
739 1745314774
740 1752414349
741 1759533151
742 1766671206
743 1773828540
744 1781005179
745 1788201149
746 1795416476
747 1802651186
748 1809905305
749 1817178859
750 1824471874
751 1831784376
752 1839116391
753 1846467945
754 1853839064
755 1861229774
756 1868640101
757 1876070071
758 1883519710
759 1890989044
760 1898478099
761 1905986901
762 1913515476
763 1921063850
764 1928632049
765 1936220099
766 1943828026
767 1951455856
768 1959103615
769 1966771329
770 1974459024
771 1982166726
772 1989894461
773 1997642255
774 2005410134
775 2013198124
776 2021006251
777 2028834541
778 2036683020
779 2044551714
780 2052440649
781 2060349851
782 2068279346
783 2076229160
784 2084199319
785 2092189849
786 2100200776
787 2108232126
788 2116283925
789 2124356199
790 2132448974
791 2140562276
792 2148696131
793 2156850565
794 2165025604
795 2173221274
796 2181437601
797 2189674611
798 2197932330
799 2206210784
800 2214509999
801 2222830001
802 2231170816
803 2239532470
804 2247914989
805 2256318399
806 2264742726
807 2273187996
808 2281654235
809 2290141469
810 2298649724
811 2307179026
812 2315729401
813 2324300875
814 2332893474
815 2341507224
816 2350142151
817 2358798281
818 2367475640
819 2376174254
820 2384894149
821 2393635351
822 2402397886
823 2411181780
824 2419987059
825 2428813749
826 2437661876
827 2446531466
828 2455422545
829 2464335139
830 2473269274
831 2482224976
832 2491202271
833 2500201185
834 2509221744
835 2518263974
836 2527327901
837 2536413551
838 2545520950
839 2554650124
840 2563801099
841 2572973901
842 2582168556
843 2591385090
844 2600623529
845 2609883899
846 2619166226
847 2628470536
848 2637796855
849 2647145209
850 2656515624
851 2665908126
852 2675322741
853 2684759495
854 2694218414
855 2703699524
856 2713202851
857 2722728421
858 2732276260
859 2741846394
860 2751438849
861 2761053651
862 2770690826
863 2780350400
864 2790032399
865 2799736849
866 2809463776
867 2819213206
868 2828985165
869 2838779679
870 2848596774
871 2858436476
872 2868298811
873 2878183805
874 2888091484
875 2898021874
876 2907975001
877 2917950891
878 2927949570
879 2937971064
880 2948015399
881 2958082601
882 2968172696
883 2978285710
884 2988421669
885 2998580599
886 3008762526
887 3018967476
888 3029195475
889 3039446549
890 3049720724
891 3060018026
892 3070338481
893 3080682115
894 3091048954
895 3101439024
896 3111852351
897 3122288961
898 3132748880
899 3143232134
900 3153738749
901 3164268751
902 3174822166
903 3185399020
904 3195999339
905 3206623149
906 3217270476
907 3227941346
908 3238635785
909 3249353819
910 3260095474
911 3270860776
912 3281649751
913 3292462425
914 3303298824
915 3314158974
916 3325042901
917 3335950631
918 3346882190
919 3357837604
920 3368816899
921 3379820101
922 3390847236
923 3401898330
924 3412973409
925 3424072499
926 3435195626
927 3446342816
928 3457514095
929 3468709489
930 3479929024
931 3491172726
932 3502440621
933 3513732735
934 3525049094
935 3536389724
936 3547754651
937 3559143901
938 3570557500
939 3581995474
940 3593457849
941 3604944651
942 3616455906
943 3627991640
944 3639551879
945 3651136649
946 3662745976
947 3674379886
948 3686038405
949 3697721559
950 3709429374
951 3721161876
952 3732919091
953 3744701045
954 3756507764
955 3768339274
956 3780195601
957 3792076771
958 3803982810
959 3815913744
960 3827869599
961 3839850401
962 3851856176
963 3863886950
964 3875942749
965 3888023599
966 3900129526
967 3912260556
968 3924416715
969 3936598029
970 3948804524
971 3961036226
972 3973293161
973 3985575355
974 3997882834
975 4010215624
976 4022573751
977 4034957241
978 4047366120
979 4059800414
980 4072260149
981 4084745351
982 4097256046
983 4109792260
984 4122354019
985 4134941349
986 4147554276
987 4160192826
988 4172857025
989 4185546899
990 4198262474
991 4211003776
992 4223770831
993 4236563665
994 4249382304
995 4262226774
996 4275097101
997 4287993311
998 4300915430
999 4313863484
1000 4326837499