3 3
4 12
5 60
6 240
7 756
8 1988
9 4572
10 9495
11 18205
12 32736
13 55848
14 91182
15 143430
16 218520
17 323816
18 468333
19 662967
20 920740
21 1257060
22 1689996
23 2240568
24 2933052
25 3795300
26 4859075
27 6160401
28 7739928
29 9643312
30 11921610
31 14631690
32 17836656
33 21606288
34 26017497
35 31154795
36 37110780
37 43986636
38 51892648
39 60948732
40 71284980
41 83042220
42 96372591
43 111440133
44 128421392
45 147506040
46 168897510
47 192813646
48 219487368
49 249167352
50 282118725
51 318623775
52 358982676
53 403514228
54 452556612
55 506468160
56 565628140
57 630437556
58 701319963
59 778722297
60 863115720
61 954996480
62 1054886786
63 1163335698
64 1280920032
65 1408245280
66 1545946545
67 1694689491
68 1855171308
69 2028121692
70 2214303840
71 2414515460
72 2629589796
73 2860396668
74 3107843527
75 3372876525
76 3656481600
77 3959685576
78 4283557278
79 4629208662
80 4997795960
81 5390520840
82 5808631581
83 6253424263
84 6726243972
85 7228486020
86 7761597180
87 8327076936
88 8926478748
89 9561411332
90 10233539955
91 10944587745
92 11696337016
93 12490630608
94 13329373242
95 14214532890
96 15148142160
97 16132299696
98 17169171593
99 18260992827
100 19410068700
101 20618776300
102 21889565976
103 23224962828
104 24627568212
105 26100061260
106 27645200415
107 29265824981
108 30964856688
109 32745301272
110 34610250070
111 36562881630
112 38606463336
113 40744353048
114 42980000757
115 45316950255
116 47758840820
117 50309408916
118 52972489908
119 55752019792
120 58652036940
121 61676683860
122 64830208971
123 68116968393
124 71541427752
125 75108164000
126 78821867250
127 82687342626
128 86709512128
129 90893416512
130 95244217185
131 99767198115
132 104467767756
133 109351460988
134 114423941072
135 119691001620
136 125158568580
137 130832702236
138 136719599223
139 142825594557
140 149157163680
141 155720924520
142 162523639566
143 169572217958
144 176873717592
145 184435347240
146 192264468685
147 200368598871
148 208755412068
149 217432742052
150 226408584300
151 235691098200
152 245288609276
153 255209611428
154 265462769187
155 276056919985
156 287001076440
157 298304428656
158 309976346538
159 322026382122
160 334464271920
161 347299939280
162 360543496761
163 374205248523
164 388295692732
165 402825523980
166 417805635720
167 433247122716
168 449161283508
169 465559622892
170 482453854415
171 499855902885
172 517777906896
173 536232221368
174 555231420102
175 574788298350
176 594915875400
177 615627397176
178 636936338853
179 658856407487
180 681401544660
181 704585929140
182 728423979556
183 752930357088
184 778119968172
185 804007967220
186 830609759355
187 857941003161
188 886017613448
189 914855764032
190 944471890530
191 974882693170
192 1006105139616
193 1038156467808
194 1071054188817
195 1104816089715
196 1139460236460
197 1175004976796
198 1211468943168
199 1248871055652
200 1287230524900
201 1326566855100
202 1366899846951
203 1408249600653
204 1450636518912
205 1494081309960
206 1538604990590
207 1584228889206
208 1630974648888
209 1678864230472
210 1727919915645
211 1778164310055
212 1829620346436
213 1882311287748
214 1936260730332
215 1991492607080
216 2048031190620
217 2105901096516
218 2165127286483
219 2225735071617
220 2287750115640
221 2351198438160
222 2416106417946
223 2482500796218
224 2550408679952
225 2619857545200
226 2690875240425
227 2763489989851
228 2837730396828
229 2913625447212
230 2991204512760
231 3070497354540
232 3151534126356
233 3234345378188
234 3318962059647
235 3405415523445
236 3493737528880
237 3583960245336
238 3676116255798
239 3770238560382
240 3866360579880
241 3964516159320
242 4064739571541
243 4167065520783
244 4271529146292
245 4378166025940
246 4487012179860
247 4598104074096
248 4711478624268
249 4827173199252
250 4945225624875
251 5065674187625
252 5188557638376
253 5313915196128
254 5441786551762
255 5572211871810
256 5705231802240
257 5840887472256
258 5979220498113
259 6120272986947
260 6264087540620
261 6410707259580
262 6560175746736
263 6712537111348
264 6867835972932
265 7026117465180
266 7187427239895
267 7351811470941
268 7519316858208
269 7689990631592
270 7863880554990
271 8041034930310
272 8221502601496
273 8405332958568
274 8592575941677
275 8783282045175
276 8977502321700
277 9175288386276
278 9376692420428
279 9581767176312
280 9790565980860
281 10003142739940
282 10219551942531
283 10439848664913
284 10664088574872
285 10892327935920
286 11124623611530
287 11361033069386
288 11601614385648
289 11846426249232
290 12095527966105
291 12348979463595
292 12606841294716
293 12869174642508
294 13136041324392
295 13407503796540
296 13683625158260
297 13964469156396
298 14250100189743
299 14540583313477
300 14835984243600
301 15136369361400
302 15441805717926
303 15752361038478
304 16068103727112
305 16389102871160
306 16715428245765
307 17047150318431
308 17384340253588
309 17727069917172
310 18075411881220
311 18429439428480
312 18789226557036
313 19154847984948
314 19526379154907
315 19903896238905
316 20287476142920
317 20677196511616
318 21073135733058
319 21475372943442
320 21883988031840
321 22299061644960
322 22720675191921
323 23148910849043
324 23583851564652
325 24025581063900
326 24474183853600
327 24929745227076
328 25392351269028
329 25862088860412
330 26339045683335
331 26823310225965
332 27314971787456
333 27814120482888
334 28320847248222
335 28835243845270
336 29357402866680
337 29887417740936
338 30425382737373
339 30971392971207
340 31525544408580
341 32087933871620
342 32658659043516
343 33237818473608
344 33825511582492
345 34421838667140
346 35026900906035
347 35640800364321
348 36263639998968
349 36895523663952
350 37536556115450
351 38186843017050
352 38846490944976
353 39515607393328
354 40194300779337
355 40882680448635
356 41580856680540
357 42288940693356
358 43007044649688
359 43735281661772
360 44473765796820
361 45222612082380
362 45981936511711
363 46751856049173
364 47532488635632
365 48323953193880
366 49126369634070
367 49939858859166
368 50764542770408
369 51600544272792
370 52447987280565
371 53306996722735
372 54177698548596
373 55060219733268
374 55954688283252
375 56861233242000
376 57779984695500
377 58711073777876
378 59654632677003
379 60610794640137
380 61579693979560
381 62561466078240
382 63556247395506
383 64564175472738
384 65585388939072
385 66620027517120
386 67668232028705
387 68730144400611
388 69805907670348
389 70895665991932
390 71999564641680
391 73117750024020
392 74250369677316
393 75397572279708
394 76559507654967
395 77736326778365
396 78928181782560
397 80135225963496
398 81357613786318
399 82595500891302
400 83849044099800
401 85118401420200
402 86403732053901
403 87705196401303
404 89022956067812
405 90357173869860
406 91708013840940
407 93075641237656
408 94460222545788
409 95861925486372
410 97280919021795
411 98717373361905
412 100171459970136
413 101643351569648
414 103133222149482
415 104641246970730
416 106167602572720
417 107712466779216
418 109276018704633
419 110858438760267
420 112459908660540
421 114080611429260
422 115720731405896
423 117380454251868
424 119059966956852
425 120759457845100
426 122479116581775
427 124219134179301
428 125979703003728
429 127761016781112
430 129563270603910
431 131386660937390
432 133231385626056
433 135097643900088
434 136985636381797
435 138895565092095
436 140827633456980
437 142782046314036
438 144759009918948
439 146758731952032
440 148781421524780
441 150827289186420
442 152896546930491
443 154989408201433
444 157106087901192
445 159246802395840
446 161411769522210
447 163601208594546
448 165815340411168
449 168054387261152
450 170318572931025
451 172608122711475
452 174923263404076
453 177264223328028
454 179631232326912
455 182024521775460
456 184444324586340
457 186890875216956
458 189364409676263
459 191865165531597
460 194393381915520
461 196949299532680
462 199533160666686
463 202145209186998
464 204785690555832
465 207454851835080
466 210152941693245
467 212880210412391
468 215636909895108
469 218423293671492
470 221239616906140
471 224086136405160
472 226963110623196
473 229870799670468
474 232809465319827
475 235779371013825
476 238780781871800
477 241813964696976
478 244879187983578
479 247976721923962
480 251106838415760
481 254269811069040
482 257465915213481
483 260695427905563
484 263958627935772
485 267255795835820
486 270587213885880
487 273953166121836
488 277353938342548
489 280789818117132
490 284261094792255
491 287768059499445
492 291311005162416
493 294890226504408
494 298506020055542
495 302158684160190
496 305848518984360
497 309575826523096
498 313340910607893
499 317144076914127
500 320985632968500
501 324865888156500
502 328785153729876
503 332743742814128
504 336741970416012
505 340780153431060
506 344858610651115
507 348977662771881
508 353137632400488
509 357338844063072
510 361581624212370
511 365866301235330
512 370193205460736
513 374562669166848
514 378975026589057
515 383430613927555
516 387929769355020
517 392472833024316
518 397060147076208
519 401692055647092
520 406368904876740
521 411091042916060
522 415858819934871
523 420672588129693
524 425532701731552
525 430439517013800
526 435393392299950
527 440394687971526
528 445443766475928
529 450540992334312
530 455686732149485
531 460881354613815
532 466125230517156
533 471418732754788
534 476762236335372
535 482156118388920
536 487600758174780
537 493096537089636
538 498643838675523
539 504243048627857
540 509894554803480
541 515598747228720
542 521356018107466
543 527166761829258
544 533031374977392
545 538950256337040
546 544923806903385
547 550952429889771
548 557036530735868
549 563176517115852
550 569372798946600
551 575625788395900
552 581935899890676
553 588303550125228
554 594729158069487
555 601213144977285
556 607755934394640
557 614357952168056
558 621019626452838
559 627741387721422
560 634523668771720
561 641366904735480
562 648271533086661
563 655237993649823
564 662266728608532
565 669358182513780
566 676512802292420
567 683731037255616
568 691013339107308
569 698360161952692
570 705771962306715
571 713249199102585
572 720792333700296
573 728401829895168
574 736078153926402
575 743821774485650
576 751633162725600
577 759512792268576
578 767461139215153
579 775478682152787
580 783565902164460
581 791723282837340
582 799951310271456
583 808250473088388
584 816621262439972
585 825064172017020
586 833579698058055
587 842168339358061
588 850830597277248
589 859566975749832
590 868377981292830
591 877264123014870
592 886225912625016
593 895263864441608
594 904378495401117
595 913570325067015
596 922839875638660
597 932187671960196
598 941614241529468
599 951120114506952
600 960705823724700
601 970371904695300
602 980118895620851
603 989947337401953
604 999857773646712
605 1009850750679760
606 1019926817551290
607 1030086526046106
608 1040330430692688
609 1050659088772272
610 1061073060327945
611 1071572908173755
612 1082159197903836
613 1092832497901548
614 1103593379348632
615 1114442416234380
616 1125380185364820
617 1136407266371916
618 1147524241722783
619 1158731696728917
620 1170030219555440
621 1181420401230360
622 1192902835653846
623 1204478119607518
624 1216146852763752
625 1227909637695000
626 1239767079883125
627 1251719787728751
628 1263768372560628
629 1275913448645012
630 1288155633195060
631 1300495546380240
632 1312933811335756
633 1325471054171988
634 1338107903983947
635 1350844992860745
636 1363682955895080
637 1376622431192736
638 1389664059882098
639 1402808486123682
640 1416056357119680
641 1429408323123520
642 1442865037449441
643 1456427156482083
644 1470095339686092
645 1483870249615740
646 1497752551924560
647 1511742915374996
648 1525842011848068
649 1540050516353052
650 1554369107037175
651 1568798465195325
652 1583339275279776
653 1597992224909928
654 1612758004882062
655 1627637309179110
656 1642630834980440
657 1657739282671656
658 1672963355854413
659 1688303761356247
660 1703761209240420
661 1719336412815780
662 1735030088646636
663 1750842956562648
664 1766775739668732
665 1782829164354980
666 1799003960306595
667 1815300860513841
668 1831720601282008
669 1848263922241392
670 1864931566357290
671 1881724279940010
672 1898642812654896
673 1915687917532368
674 1932860350977977
675 1950160872782475
676 1967590246131900
677 1985149237617676
678 2002838617246728
679 2020659158451612
680 2038611638100660
681 2056696836508140
682 2074915537444431
683 2093268528146213
684 2111756599326672
685 2130380545185720
686 2149141163420230
687 2168039255234286
688 2187075625349448
689 2206251082015032
690 2225566437018405
691 2245022505695295
692 2264620106940116
693 2284360063216308
694 2304243200566692
695 2324270348623840
696 2344442340620460
697 2364760013399796
698 2385224207426043
699 2405835766794777
700 2426595539243400
701 2447504376161600
702 2468563132601826
703 2489772667289778
704 2511133842634912
705 2532647524740960
706 2554314583416465
707 2576135892185331
708 2598112328297388
709 2620244772738972
710 2642534110243520
711 2664981229302180
712 2687587022174436
713 2710352384898748
714 2733278217303207
715 2756365423016205
716 2779614909477120
717 2803027587947016
718 2826604373519358
719 2850346185130742
720 2874253945571640
721 2898328581497160
722 2922571023437821
723 2946982205810343
724 2971563066928452
725 2996314549013700
726 3021237598206300
727 3046333164575976
728 3071602202132828
729 3097045668838212
730 3122664526615635
731 3148459741361665
732 3174432282956856
733 3200583125276688
734 3226913246202522
735 3253423627632570
736 3280115255492880
737 3306989119748336
738 3334046214413673
739 3361287537564507
740 3388714091348380
741 3416326881995820
742 3444126919831416
743 3472115219284908
744 3500292798902292
745 3528660681356940
746 3557219893460735
747 3585971466175221
748 3614916434622768
749 3644055838097752
750 3673390720077750
751 3702922128234750
752 3732651114446376
753 3762578734807128
754 3792706049639637
755 3823034123505935
756 3853564025218740
757 3884296827852756
758 3915233608755988
759 3946375449561072
760 3977723436196620
761 4009278658898580
762 4041042212221611
763 4073015195050473
764 4105198710611432
765 4137593866483680
766 4170201774610770
767 4203023551312066
768 4236060317294208
769 4269313197662592
770 4302783321932865
771 4336471824042435
772 4370379842361996
773 4404508519707068
774 4438859003349552
775 4473432445029300
776 4508230000965700
777 4543252831869276
778 4578502102953303
779 4613978983945437
780 4649684649099360
781 4685620277206440
782 4721787051607406
783 4758186160204038
784 4794818795470872
785 4831686154466920
786 4868789438847405
787 4906129854875511
788 4943708613434148
789 4981526930037732
790 5019586024843980
791 5057887122665720
792 5096431452982716
793 5135220249953508
794 5174254752427267
795 5213536203955665
796 5253065852804760
797 5292844951966896
798 5332874759172618
799 5373156536902602
800 5413691552399600
801 5454481077680400
802 5495526389547801
803 5536828769602603
804 5578389504255612
805 5620209884739660
806 5662291207121640
807 5704634772314556
808 5747241886089588
809 5790113859088172
810 5833252006834095
811 5876657649745605
812 5920332113147536
813 5964276727283448
814 6008492827327782
815 6052981753398030
816 6097744850566920
817 6142783468874616
818 6188098963340933
819 6233692693977567
820 6279566025800340
821 6325720328841460
822 6372156978161796
823 6418877353863168
824 6465882841100652
825 6513174830094900
826 6560754716144475
827 6608623899638201
828 6656783786067528
829 6705235786038912
830 6753981315286210
831 6803021794683090
832 6852358650255456
833 6901993313193888
834 6951927219866097
835 7002161811829395
836 7052698535843180
837 7103538843881436
838 7154684193145248
839 7206136046075332
840 7257895870364580
841 7309965138970620
842 7362345330128391
843 7415037927362733
844 7468044419500992
845 7521366300685640
846 7575005070386910
847 7628962233415446
848 7683239299934968
849 7737837785474952
850 7792759210943325
851 7848005102639175
852 7903576992265476
853 7959476416941828
854 8015704919217212
855 8072264047082760
856 8129155353984540
857 8186380398836356
858 8243940746032563
859 8301837965460897
860 8360073632515320
861 8418649328108880
862 8477566638686586
863 8536827156238298
864 8596432478311632
865 8656384208024880
866 8716683954079945
867 8777333330775291
868 8838333958018908
869 8899687461341292
870 8961395471908440
871 9023459626534860
872 9085881567696596
873 9148662943544268
874 9211805407916127
875 9275310620351125
876 9339180246102000
877 9403415956148376
878 9468019427209878
879 9532992341759262
880 9598336388035560
881 9664053260057240
882 9730144657635381
883 9796612286386863
884 9863457857747572
885 9930683088985620
886 9998289703214580
887 10066279429406736
888 10134654002406348
889 10203415162942932
890 10272564657644555
891 10342104239051145
892 10412035665627816
893 10482360701778208
894 10553081117857842
895 10624198690187490
896 10695715201066560
897 10767632438786496
898 10839952197644193
899 10912676277955427
900 10985806486068300
901 11059344634376700
902 11133292541333776
903 11207652031465428
904 11282424935383812
905 11357613089800860
906 11433218337541815
907 11509242527558781
908 11585687514944288
909 11662555160944872
910 11739847332974670
911 11817565904629030
912 11895712755698136
913 11974289772180648
914 12053298846297357
915 12132741876504855
916 12212620767509220
917 12292937430279716
918 12373693782062508
919 12454891746394392
920 12536533253116540
921 12618620238388260
922 12701154644700771
923 12784138420890993
924 12867573522155352
925 12951461910063600
926 13035805552572650
927 13120606424040426
928 13205866505239728
929 13291587783372112
930 13377772252081785
931 13464421911469515
932 13551538768106556
933 13639124835048588
934 13727182131849672
935 13815712684576220
936 13904718525820980
937 13994201694717036
938 14084164236951823
939 14174608204781157
940 14265535657043280
941 14356948659172920
942 14448849283215366
943 14541239607840558
944 14634121718357192
945 14727497706726840
946 14821369671578085
947 14915739718220671
948 15010609958659668
949 15105982511609652
950 15201859502508900
951 15298243063533600
952 15395135333612076
953 15492538458439028
954 15590454590489787
955 15688885889034585
956 15787834520152840
957 15887302656747456
958 15987292478559138
959 16087806172180722
960 16188845931071520
961 16290413955571680
962 16392512452916561
963 16495143637251123
964 16598309729644332
965 16702012958103580
966 16806255557589120
967 16911039770028516
968 17016367844331108
969 17122242036402492
970 17228664609159015
971 17335637832542285
972 17443163983533696
973 17551245346168968
974 17659884211552702
975 17769082877872950
976 17878843650415800
977 17989168841579976
978 18100060770891453
979 18211521765018087
980 18323554157784260
981 18436160290185540
982 18549342510403356
983 18663103173819688
984 18777444643031772
985 18892369287866820
986 19007879485396755
987 19123977619952961
988 19240666083141048
989 19357947273855632
990 19475823598295130
991 19594297469976570
992 19713371309750416
993 19833047545815408
994 19953328613733417
995 20074216956444315
996 20195715024280860
997 20317825274983596
998 20440550173715768
999 20563892193078252
1000 20687853813124500