3 3
4 16
5 51
6 126
7 266
8 504
9 882
10 1452
11 2277
12 3432
13 5005
14 7098
15 9828
16 13328
17 17748
18 23256
19 30039
20 38304
21 48279
22 60214
23 74382
24 91080
25 110630
26 133380
27 159705
28 190008
29 224721
30 264306
31 309256
32 360096
33 417384
34 481712
35 553707
36 634032
37 723387
38 822510
39 932178
40 1053208
41 1186458
42 1332828
43 1493261
44 1668744
45 1860309
46 2069034
47 2296044
48 2542512
49 2809660
50 3098760
51 3411135
52 3748160
53 4111263
54 4501926
55 4921686
56 5372136
57 5854926
58 6371764
59 6924417
60 7514712
61 8144537
62 8815842
63 9530640
64 10291008
65 11099088
66 11957088
67 12867283
68 13832016
69 14853699
70 15934814
71 17077914
72 18285624
73 19560642
74 20905740
75 22323765
76 23817640
77 25390365
78 27045018
79 28784756
80 30612816
81 32532516
82 34547256
83 36660519
84 38875872
85 41196967
86 43627542
87 46171422
88 48832520
89 51614838
90 54522468
91 57559593
92 60730488
93 64039521
94 67491154
95 71089944
96 74840544
97 78747704
98 82816272
99 87051195
100 91457520
101 96040395
102 100805070
103 105756898
104 110901336
105 116243946
106 121790396
107 127546461
108 133518024
109 139711077
110 146131722
111 152786172
112 159680752
113 166821900
114 174216168
115 181870223
116 189790848
117 197984943
118 206459526
119 215221734
120 224278824
121 233638174
122 243307284
123 253293777
124 263605400
125 274250025
126 285235650
127 296570400
128 308262528
129 320320416
130 332752576
131 345567651
132 358774416
133 372381779
134 386398782
135 400834602
136 415698552
137 431000082
138 446748780
139 462954373
140 479626728
141 496775853
142 514411898
143 532545156
144 551186064
145 570345204
146 590033304
147 610261239
148 631040032
149 652380855
150 674295030
151 696794030
152 719889480
153 743593158
154 767916996
155 792873081
156 818473656
157 844731121
158 871658034
159 899267112
160 927571232
161 956583432
162 986316912
163 1016785035
164 1048001328
165 1079979483
166 1112733358
167 1146276978
168 1180624536
169 1215790394
170 1251789084
171 1288635309
172 1326343944
173 1364930037
174 1404408810
175 1444795660
176 1486106160
177 1528356060
178 1571561288
179 1615737951
180 1660902336
181 1707070911
182 1754260326
183 1802487414
184 1851769192
185 1902122862
186 1953565812
187 2006115617
188 2059790040
189 2114607033
190 2170584738
191 2227741488
192 2286095808
193 2345666416
194 2406472224
195 2468532339
196 2531866064
197 2596492899
198 2662432542
199 2729704890
200 2798330040
201 2868328290
202 2939720140
203 3012526293
204 3086767656
205 3162465341
206 3239640666
207 3318315156
208 3398510544
209 3480248772
210 3563551992
211 3648442567
212 3734943072
213 3823076295
214 3912865238
215 4004333118
216 4097503368
217 4192399638
218 4289045796
219 4387465929
220 4487684344
221 4589725569
222 4693614354
223 4799375672
224 4907034720
225 5016616920
226 5128147920
227 5241653595
228 5357160048
229 5474693611
230 5594280846
231 5715948546
232 5839723736
233 5965633674
234 6093705852
235 6223967997
236 6356448072
237 6491174277
238 6628175050
239 6767479068
240 6909115248
241 7053112748
242 7199500968
243 7348309551
244 7499568384
245 7653307599
246 7809557574
247 7968348934
248 8129712552
249 8293679550
250 8460281300
251 8629549425
252 8801515800
253 8976212553
254 9153672066
255 9333926976
256 9517010176
257 9702954816
258 9891794304
259 10083562307
260 10278292752
261 10476019827
262 10676777982
263 10880601930
264 11087526648
265 11297587378
266 11510819628
267 11727259173
268 11946942056
269 12169904589
270 12396183354
271 12625815204
272 12858837264
273 13095286932
274 13335201880
275 13578620055
276 13825579680
277 14076119255
278 14330277558
279 14588093646
280 14849606856
281 15114856806
282 15383883396
283 15656726809
284 15933427512
285 16214026257
286 16498564082
287 16787082312
288 17079622560
289 17376226728
290 17676937008
291 17981795883
292 18290846128
293 18604130811
294 18921693294
295 19243577234
296 19569826584
297 19900485594
298 20235598812
299 20575211085
300 20919367560
301 21268113685
302 21621495210
303 21979558188
304 22342348976
305 22709914236
306 23082300936
307 23459556351
308 23841728064
309 24228863967
310 24621012262
311 25018221462
312 25420540392
313 25828018190
314 26240704308
315 26658648513
316 27081900888
317 27510511833
318 27944532066
319 28384012624
320 28829004864
321 29279560464
322 29735731424
323 30197570067
324 30665129040
325 31138461315
326 31617620190
327 32102659290
328 32593632568
329 33090594306
330 33593599116
331 34102701941
332 34617958056
333 35139423069
334 35667152922
335 36201203892
336 36741632592
337 37288495972
338 37841851320
339 38401756263
340 38968268768
341 39541447143
342 40121350038
343 40708036446
344 41301565704
345 41901997494
346 42509391844
347 43123809129
348 43745310072
349 44373955745
350 45009807570
351 45652927320
352 46303377120
353 46961219448
354 47626517136
355 48299333371
356 48979731696
357 49667776011
358 50363530574
359 51067060002
360 51778429272
361 52497703722
362 53224949052
363 53960231325
364 54703616968
365 55455172773
366 56214965898
367 56983063868
368 57759534576
369 58544446284
370 59337867624
371 60139867599
372 60950515584
373 61769881327
374 62598034950
375 63435046950
376 64280988200
377 65135929950
378 65999943828
379 66873101841
380 67755476376
381 68647140201
382 69548166466
383 70458628704
384 71378600832
385 72308157152
386 73247372352
387 74196321507
388 75155080080
389 76123723923
390 77102329278
391 78090972778
392 79089731448
393 80098682706
394 81117904364
395 82147474629
396 83187472104
397 84237975789
398 85299065082
399 86370819780
400 87453320080
401 88546646580
402 89650880280
403 90766102583
404 91892395296
405 93029840631
406 94178521206
407 95338520046
408 96509920584
409 97692806662
410 98887262532
411 100093372857
412 101311222712
413 102540897585
414 103782483378
415 105036066408
416 106301733408
417 107579571528
418 108869668336
419 110172111819
420 111486990384
421 112814392859
422 114154408494
423 115507126962
424 116872638360
425 118251033210
426 119642402460
427 121046837485
428 122464430088
429 123895272501
430 125339457386
431 126797077836
432 128268227376
433 129752999964
434 131251489992
435 132763792287
436 134290002112
437 135830215167
438 137384527590
439 138953035958
440 140535837288
441 142133029038
442 143744709108
443 145370975841
444 147011928024
445 148667664889
446 150338286114
447 152023891824
448 153724582592
449 155440459440
450 157171623840
451 158918177715
452 160680223440
453 162457863843
454 164251202206
455 166060342266
456 167885388216
457 169726444706
458 171583616844
459 173457010197
460 175346730792
461 177252885117
462 179175580122
463 181114923220
464 183071022288
465 185043985668
466 187033922168
467 189040941063
468 191065152096
469 193106665479
470 195165591894
471 197242042494
472 199336128904
473 201447963222
474 203577658020
475 205725326345
476 207891081720
477 210075038145
478 212277310098
479 214498012536
480 216737260896
481 218995171096
482 221271859536
483 223567443099
484 225882039152
485 228215765547
486 230568740622
487 232941083202
488 235332912600
489 237744348618
490 240175511548
491 242626522173
492 245097501768
493 247588572101
494 250099855434
495 252631474524
496 255183552624
497 257756213484
498 260349581352
499 262963780975
500 265598937600
501 268255176975
502 270932625350
503 273631409478
504 276351656616
505 279093494526
506 281857051476
507 284642456241
508 287449838104
509 290279326857
510 293131052802
511 296005146752
512 298901740032
513 301820964480
514 304762952448
515 307727836803
516 310715750928
517 313726828723
518 316761204606
519 319819013514
520 322900390904
521 326005472754
522 329134395564
523 332287296357
524 335464312680
525 338665582605
526 341891244730
527 345141438180
528 348416302608
529 351715978196
530 355040605656
531 358390326231
532 361765281696
533 365165614359
534 368591467062
535 372042983182
536 375520306632
537 379023581862
538 382552953860
539 386108568153
540 389690570808
541 393299108433
542 396934328178
543 400596377736
544 404285405344
545 408001559784
546 411744990384
547 415515847019
548 419314280112
549 423140440635
550 426994480110
551 430876550610
552 434786804760
553 438725395738
554 442692477276
555 446688203661
556 450712729736
557 454766210901
558 458848803114
559 462960662892
560 467101947312
561 471272814012
562 475473421192
563 479703927615
564 483964492608
565 488255276063
566 492576438438
567 496928140758
568 501310544616
569 505723812174
570 510168106164
571 514643589889
572 519150427224
573 523688782617
574 528258821090
575 532860708240
576 537494610240
577 542160693840
578 546859126368
579 551590075731
580 556353710416
581 561150199491
582 565979712606
583 570842419994
584 575738492472
585 580668101442
586 585631418892
587 590628617397
588 595659870120
589 600725350813
590 605825233818
591 610959694068
592 616128907088
593 621333048996
594 626572296504
595 631846826919
596 637156818144
597 642502448679
598 647883897622
599 653301344670
600 658754970120
601 664244954870
602 669771480420
603 675334728873
604 680934882936
605 686572125921
606 692246641746
607 697958614936
608 703708230624
609 709495674552
610 715321133072
611 721184793147
612 727086842352
613 733027468875
614 739006861518
615 745025209698
616 751082703448
617 757179533418
618 763315890876
619 769491967709
620 775707956424
621 781964050149
622 788260442634
623 794597328252
624 800974902000
625 807393359500
626 813852897000
627 820353711375
628 826896000128
629 833479961391
630 840105793926
631 846773697126
632 853483871016
633 860236516254
634 867031834132
635 873870026577
636 880751296152
637 887675846057
638 894643880130
639 901655602848
640 908711219328
641 915810935328
642 922954957248
643 930143492131
644 937376747664
645 944654932179
646 951978254654
647 959346924714
648 966761152632
649 974221149330
650 981727126380
651 989279296005
652 996877871080
653 1004523065133
654 1012215092346
655 1019954167556
656 1027740506256
657 1035574324596
658 1043455839384
659 1051385268087
660 1059362828832
661 1067388740407
662 1075463222262
663 1083586494510
664 1091758777928
665 1099980293958
666 1108251264708
667 1116571912953
668 1124942462136
669 1133363136369
670 1141834160434
671 1150355759784
672 1158928160544
673 1167551589512
674 1176226274160
675 1184952442635
676 1193730323760
677 1202560147035
678 1211442142638
679 1220376541426
680 1229363574936
681 1238403475386
682 1247496475676
683 1256642809389
684 1265842710792
685 1275096414837
686 1284404157162
687 1293766174092
688 1303182702640
689 1312653980508
690 1322180246088
691 1331761738463
692 1341398697408
693 1351091363391
694 1360839977574
695 1370644781814
696 1380506018664
697 1390423931374
698 1400398763892
699 1410430760865
700 1420520167640
701 1430667230265
702 1440872195490
703 1451135310768
704 1461456824256
705 1471836984816
706 1482276042016
707 1492774246131
708 1503331848144
709 1513949099747
710 1524626253342
711 1535363562042
712 1546161279672
713 1557019660770
714 1567938960588
715 1578919435093
716 1589961340968
717 1601064935613
718 1612230477146
719 1623458224404
720 1634748436944
721 1646101375044
722 1657517299704
723 1668996472647
724 1680539156320
725 1692145613895
726 1703816109270
727 1715550907070
728 1727350272648
729 1739214472086
730 1751143772196
731 1763138440521
732 1775198745336
733 1787324955649
734 1799517341202
735 1811776172472
736 1824101720672
737 1836494257752
738 1848954056400
739 1861481390043
740 1874076532848
741 1886739759723
742 1899471346318
743 1912271569026
744 1925140704984
745 1938079032074
746 1951086828924
747 1964164374909
748 1977311950152
749 1990529835525
750 2003818312650
751 2017177663900
752 2030608172400
753 2044110122028
754 2057683797416
755 2071329483951
756 2085047467776
757 2098838035791
758 2112701475654
759 2126638075782
760 2140648125352
761 2154731914302
762 2168889733332
763 2183121873905
764 2197428628248
765 2211810289353
766 2226267150978
767 2240799507648
768 2255407654656
769 2270091888064
770 2284852504704
771 2299689802179
772 2314604078864
773 2329595633907
774 2344664767230
775 2359811779530
776 2375036972280
777 2390340647730
778 2405723108908
779 2421184659621
780 2436725604456
781 2452346248781
782 2468046898746
783 2483827861284
784 2499689444112
785 2515631955732
786 2531655705432
787 2547761003287
788 2563948160160
789 2580217487703
790 2596569298358
791 2613003905358
792 2629521622728
793 2646122765286
794 2662807648644
795 2679576589209
796 2696429904184
797 2713367911569
798 2730390930162
799 2747499279560
800 2764693280160
801 2781973253160
802 2799339520560
803 2816792405163
804 2834332230576
805 2851959321211
806 2869674002286
807 2887476599826
808 2905367440664
809 2923346852442
810 2941415163612
811 2959572703437
812 2977819801992
813 2996156790165
814 3014583999658
815 3033101762988
816 3051710413488
817 3070410285308
818 3089201713416
819 3108085033599
820 3127060582464
821 3146128697439
822 3165289716774
823 3184543979542
824 3203891825640
825 3223333595790
826 3242869631540
827 3262500275265
828 3282225870168
829 3302046760281
830 3321963290466
831 3341975806416
832 3362084654656
833 3382290182544
834 3402592738272
835 3422992670867
836 3443490330192
837 3464086066947
838 3484780232670
839 3505573179738
840 3526465261368
841 3547456831618
842 3568548245388
843 3589739858421
844 3611032027304
845 3632425109469
846 3653919463194
847 3675515447604
848 3697213422672
849 3719013749220
850 3740916788920
851 3762922904295
852 3785032458720
853 3807245816423
854 3829563342486
855 3851985402846
856 3874512364296
857 3897144594486
858 3919882461924
859 3942726335977
860 3965676586872
861 3988733585697
862 4011897704402
863 4035169315800
864 4058548793568
865 4082036512248
866 4105632847248
867 4129338174843
868 4153152872176
869 4177077317259
870 4201111888974
871 4225256967074
872 4249512932184
873 4273880165802
874 4298359050300
875 4322949968925
876 4347653305800
877 4372469445925
878 4397398775178
879 4422441680316
880 4447598548976
881 4472869769676
882 4498255731816
883 4523756825679
884 4549373442432
885 4575105974127
886 4600954813702
887 4626920354982
888 4653002992680
889 4679203122398
890 4705521140628
891 4731957444753
892 4758512433048
893 4785186504681
894 4811980059714
895 4838893499104
896 4865927224704
897 4893081639264
898 4920357146432
899 4947754150755
900 4975273057680
901 5002914273555
902 5030678205630
903 5058565262058
904 5086575851896
905 5114710385106
906 5142969272556
907 5171352926021
908 5199861758184
909 5228496182637
910 5257256613882
911 5286143467332
912 5315157159312
913 5344298107060
914 5373566728728
915 5402963443383
916 5432488671008
917 5462142832503
918 5491926349686
919 5521839645294
920 5551883142984
921 5582057267334
922 5612362443844
923 5642799098937
924 5673367659960
925 5704068555185
926 5734902213810
927 5765869065960
928 5796969542688
929 5828204075976
930 5859573098736
931 5891077044811
932 5922716348976
933 5954491446939
934 5986402775342
935 6018450771762
936 6050635874712
937 6082958523642
938 6115419158940
939 6148018221933
940 6180756154888
941 6213633401013
942 6246650404458
943 6279807610316
944 6313105464624
945 6346544414364
946 6380124907464
947 6413847392799
948 6447712320192
949 6481720140415
950 6515871305190
951 6550166267190
952 6584605480040
953 6619189398318
954 6653918477556
955 6688793174241
956 6723813945816
957 6758981250681
958 6794295548194
959 6829757298672
960 6865366963392
961 6901125004592
962 6937031885472
963 6973088070195
964 7009294023888
965 7045650212643
966 7082157103518
967 7118815164538
968 7155624864696
969 7192586673954
970 7229701063244
971 7266968504469
972 7304389470504
973 7341964435197
974 7379693873370
975 7417578260820
976 7455618074320
977 7493813791620
978 7532165891448
979 7570674853511
980 7609341158496
981 7648165288071
982 7687147724886
983 7726288952574
984 7765589455752
985 7805049720022
986 7844670231972
987 7884451479177
988 7924393950200
989 7964498134593
990 8004764522898
991 8045193606648
992 8085785878368
993 8126541831576
994 8167461960784
995 8208546761499
996 8249796730224
997 8291212364459
998 8332794162702
999 8374542624450
1000 8416458250200