4 4
5 30
6 126
7 393
8 1016
9 2304
10 4740
11 9042
12 16236
13 27742
14 45474
15 71955
16 110448
17 165104
18 241128
19 344964
20 484500
21 669294
22 910822
23 1222749
24 1621224
25 2125200
26 2756780
27 3541590
28 4509180
29 5693454
30 7133130
31 8872231
32 10960608
33 13454496
34 16417104
35 19919240
36 24039972
37 28867326
38 34499022
39 41043249
40 48619480
41 57359328
42 67407444
43 78922458
44 92077964
45 107063550
46 124085874
47 143369787
48 165159504
49 189719824
50 217337400
51 248322060
52 283008180
53 321756110
54 364953654
55 413017605
56 466395336
57 525566448
58 591044476
59 663378654
60 743155740
61 831001902
62 927584666
63 1033614927
64 1149849024
65 1277090880
66 1416194208
67 1568064784
68 1733662788
69 1914005214
70 2110168350
71 2323290329
72 2554573752
73 2805288384
74 3076773924
75 3370442850
76 3687783340
77 4030362270
78 4399828290
79 4797914979
80 5226444080
81 5687328816
82 6182577288
83 6714295956
84 7284693204
85 7896082990
86 8550888582
87 9251646381
88 10001009832
89 10801753424
90 11656776780
91 12569108838
92 13541912124
93 14578487118
94 15682276714
95 16856870775
96 18106010784
97 19433594592
98 20843681264
99 22340496024
100 23928435300
101 25612071870
102 27396160110
103 29285641345
104 31285649304
105 33401515680
106 35638775796
107 38003174378
108 40500671436
109 43137448254
110 45919913490
111 48854709387
112 51948718096
113 55209068112
114 58643140824
115 62258577180
116 66063284468
117 70065443214
118 74273514198
119 78696245589
120 83342680200
121 88222162864
122 93344347932
123 98719206894
124 104357036124
125 110268464750
126 116464462650
127 122956348575
128 129755798400
129 136874853504
130 144325929280
131 152121823776
132 160275726468
133 168801227166
134 177712325054
135 187023437865
136 196749411192
137 206905527936
138 217507517892
139 228571567474
140 240114329580
141 252152933598
142 264704995554
143 277788628403
144 291422452464
145 305625606000
146 320417755944
147 335819108772
148 351850421524
149 368533012974
150 385888774950
151 403940183805
152 422710312040
153 442222840080
154 462502068204
155 483572928630
156 505460997756
157 528192508558
158 551794363146
159 576294145479
160 601720134240
161 628101315872
162 655467397776
163 683848821672
164 713276777124
165 743783215230
166 775400862478
167 808163234769
168 842104651608
169 877260250464
170 913666001300
171 951358721274
172 990376089612
173 1030756662654
174 1072539889074
175 1115766125275
176 1160476650960
177 1206713684880
178 1254520400760
179 1303940943404
180 1355020444980
181 1407805041486
182 1462341889398
183 1518679182501
184 1576866168904
185 1636953168240
186 1698991589052
187 1763033946366
188 1829133879452
189 1897346169774
190 1967726759130
191 2040332767983
192 2115222513984
193 2192455530688
194 2272092586464
195 2354195703600
196 2438828177604
197 2526054596702
198 2615940861534
199 2708554205049
200 2803963212600
201 2902237842240
202 3003449445220
203 3107670786690
204 3214976066604
205 3325440940830
206 3439142542466
207 3556159503363
208 3676571975856
209 3800461654704
210 3927911799240
211 4059007255732
212 4193834479956
213 4332481559982
214 4475038239174
215 4621595939405
216 4772247784488
217 4927088623824
218 5086215056268
219 5249725454214
220 5417719987900
221 5590300649934
222 5767571280042
223 5949637590039
224 6136607189024
225 6328589608800
226 6525696329520
227 6728040805560
228 6935738491620
229 7148906869054
230 7367665472430
231 7592135916321
232 7822441922328
233 8058709346336
234 8301066206004
235 8549642708490
236 8804571278412
237 9065986586046
238 9334025575762
239 9608827494699
240 9890533921680
241 10179288796368
242 10475238448664
243 10778531628348
244 11089319534964
245 11407755847950
246 11733996757014
247 12068200992757
248 12410529857544
249 12761147256624
250 13120219729500
251 13487916481550
252 13864409415900
253 14249873165550
254 14644485125754
255 15048425486655
256 15461877266176
257 15885026343168
258 16318061490816
259 16761174410304
260 17214559764740
261 17678415213342
262 18152941445886
263 18638342217417
264 19134824383224
265 19642597934080
266 20161876031748
267 20692875044754
268 21235814584428
269 21790917541214
270 22358410121250
271 22938521883219
272 23531485775472
273 24137538173424
274 24756918917224
275 25389871349700
276 26036642354580
277 26697482394990
278 27372645552230
279 28062389564829
280 28766975867880
281 29486669632656
282 30221739806508
283 30972459153046
284 31739104292604
285 32521955742990
286 33321297960522
287 34137419381351
288 34970612463072
289 35821173726624
290 36689403798480
291 37575607453128
292 38480093655844
293 39403175605758
294 40345170779214
295 41306400973425
296 42287192350424
297 43287875481312
298 44308785390804
299 45350261602074
300 46412648181900
301 47496293786110
302 48601551705330
303 49728779911035
304 50878341101904
305 52050602750480
306 53245937150136
307 54464721462348
308 55707337764276
309 56974173096654
310 58265619511990
311 59582074123077
312 60923939151816
313 62291621978352
314 63685535190524
315 65106096633630
316 66553729460508
317 68028862181934
318 69531928717338
319 71063368445839
320 72623626257600
321 74213152605504
322 75832403557152
323 77481840847184
324 79161931929924
325 80873150032350
326 82615974207390
327 84390889387545
328 86198386438840
329 88038962215104
330 89913119612580
331 91821367624866
332 93764221398188
333 95742202287006
334 97755837909954
335 99805662206115
336 101892215491632
337 104016044516656
338 106177702522632
339 108377749299924
340 110616751245780
341 112895281422638
342 115213919616774
343 117573252397293
344 119973873175464
345 122416382264400
346 124901386939084
347 127429501496742
348 130001347317564
349 132617552925774
350 135278754051050
351 137985593690295
352 140738722169760
353 143538797207520
354 146386483976304
355 149282455166680
356 152227391050596
357 155221979545278
358 158266916277486
359 161362904648129
360 164510655897240
361 167710889169312
362 170964331578996
363 174271718277162
364 177633792517324
365 181051305722430
366 184525017552018
367 188055695969739
368 191644117311248
369 195291066352464
370 198997336378200
371 202763729251164
372 206591055481332
373 210480134295694
374 214431793708374
375 218446870591125
376 222526210744200
377 226670668967600
378 230881109132700
379 235158404254254
380 239503436562780
381 243917097577326
382 248400288178618
383 252953918682591
384 257578908914304
385 262276188282240
386 267046695852992
387 271891380426336
388 276811200610692
389 281807124898974
390 286880131744830
391 292031209639273
392 297261357187704
393 302571583187328
394 307962906704964
395 313436357155250
396 318992974379244
397 324633808723422
398 330359921119074
399 336172383162099
400 342072277193200
401 348060696378480
402 354138744790440
403 360307537489380
404 366568200605204
405 372921871419630
406 379369698448806
407 385912841526333
408 392552471886696
409 399289772249104
410 406125936901740
411 413062171786422
412 420099694583676
413 427239734798222
414 434483533844874
415 441832345134855
416 449287434162528
417 456850078592544
418 464521568347408
419 472303205695464
420 480196305339300
421 488202194504574
422 496322213029262
423 504557713453329
424 512910061108824
425 521380634210400
426 529970823946260
427 538682034569530
428 547515683490060
429 556473201366654
430 565556032199730
431 574765633424411
432 584103476004048
433 593571044524176
434 603169837286904
435 612901366405740
436 622767157900852
437 632768751794766
438 642907702208502
439 653185577458149
440 663603960151880
441 674164447287408
442 684868650349884
443 695718195410238
444 706714723223964
445 717859889330350
446 729155364152154
447 740602833095727
448 752203996651584
449 763960570495424
450 775874285589600
451 787946888285040
452 800180140423620
453 812575819440990
454 825135718469854
455 837861646443705
456 850755428201016
457 863818904589888
458 877053932573156
459 890462385333954
460 904046152381740
461 917807139658782
462 931747269647106
463 945868481475907
464 960172731029424
465 974661991055280
466 989338251273288
467 1004203518484724
468 1019259816682068
469 1034509187159214
470 1049953688622150
471 1065595397300109
472 1081436407057192
473 1097478829504464
474 1113724794112524
475 1130176448324550
476 1146835957669820
477 1163705505877710
478 1180787294992170
479 1198083545486679
480 1215596496379680
481 1233328405350496
482 1251281548855728
483 1269458222246136
484 1287860739884004
485 1306491435260990
486 1325352661116462
487 1344446789556321
488 1363776212172312
489 1383343340161824
490 1403150604448180
491 1423200455801418
492 1443495364959564
493 1464037822750398
494 1484830340213714
495 1505875448724075
496 1527175700114064
497 1548733666798032
498 1570551941896344
499 1592633139360124
500 1614979894096500
501 1637594862094350
502 1660480720550550
503 1683640167996725
504 1707075924426504
505 1730790731423280
506 1754787352288476
507 1779068572170318
508 1803637198193116
509 1828496059587054
510 1853648007818490
511 1879095916720767
512 1904842682625536
513 1930891224494592
514 1957244484052224
515 1983905425918080
516 2010877037740548
517 2038162330330654
518 2065764337796478
519 2093686117678089
520 2121930751083000
521 2150501342822144
522 2179401021546372
523 2208632939883474
524 2238200274575724
525 2268106226617950
526 2298354021396130
527 2328946908826515
528 2359888163495280
529 2391181084798704
530 2422828997083880
531 2454835249789956
532 2487203217589908
533 2519936300532846
534 2553037924186854
535 2586511539782365
536 2620360624356072
537 2654588680895376
538 2689199238483372
539 2724195852444374
540 2759582104489980
541 2795361602865678
542 2831537982497994
543 2868114905142183
544 2905096059530464
545 2942485161520800
546 2980285954246224
547 3018502208264712
548 3057137721709604
549 3096196320440574
550 3135681858195150
551 3175598216740785
552 3215949306027480
553 3256739064340960
554 3297971458456404
555 3339650483792730
556 3381780164567436
557 3424364553951998
558 3467407734227826
559 3510913816942779
560 3554886943068240
561 3599331283156752
562 3644251037500216
563 3689650436288652
564 3735533739769524
565 3781905238407630
566 3828769253045558
567 3876130135064709
568 3923992266546888
569 3972360060436464
570 4021237960703100
571 4070630442505054
572 4120542012353052
573 4170977208274734
574 4221940599979674
575 4273436789024975
576 4325470408981440
577 4378046125600320
578 4431168636980640
579 4484842673737104
580 4539072999168580
581 4593864409427166
582 4649221733687838
583 4705149834318681
584 4761653607051704
585 4818737981154240
586 4876407919600932
587 4934668419246306
588 4993524510997932
589 5052981259990174
590 5113043765758530
591 5173717162414563
592 5235006618821424
593 5296917338769968
594 5359454561155464
595 5422623560154900
596 5486429645404884
597 5550878162180142
598 5615974491572614
599 5681724050671149
600 5748132292741800
601 5815204707408720
602 5882946820835660
603 5951364195908070
604 6020462432415804
605 6090247167236430
606 6160724074519146
607 6231898865869303
608 6303777290533536
609 6376365135585504
610 6449668226112240
611 6523692425401112
612 6598443635127396
613 6673927795542462
614 6750150885662574
615 6827118923458305
616 6904837966044568
617 6983314109871264
618 7062553490914548
619 7142562284868714
620 7223346707338700
621 7304913014033214
622 7387267500958482
623 7470416504612619
624 7554366402180624
625 7639123611730000
626 7724694592407000
627 7811085844633500
628 7898303910304500
629 7986355372986254
630 8075246858115030
631 8164985033196501
632 8255576608005768
633 8347028334788016
634 8439347008459804
635 8532539466810990
636 8626612590707292
637 8721573304293486
638 8817428575197242
639 8914185414733599
640 9011850878110080
641 9110432064632448
642 9209936117911104
643 9310370226068128
644 9411741621944964
645 9514057583310750
646 9617325433071294
647 9721552539478697
648 9826746316341624
649 9932914223236224
650 10040063765717700
651 10148202495532530
652 10257338010831340
653 10367477956382430
654 10478630023785954
655 10590801951688755
656 10704001525999856
657 10818236580106608
658 10933514995091496
659 11049844699949604
660 11167233671806740
661 11285689936138222
662 11405221566988326
663 11525836687190397
664 11647543468587624
665 11770350132254480
666 11894264948718828
667 12019296238184694
668 12145452370755708
669 12272741766659214
670 12401172896471050
671 12530754281340999
672 12661494493218912
673 12793402155081504
674 12926485941159824
675 13060754577167400
676 13196216840529060
677 13332881560610430
678 13470757618948110
679 13609853949480529
680 13750179538779480
681 13891743426282336
682 14034554704524948
683 14178622519375226
684 14323956070267404
685 14470564610436990
686 14618457447156402
687 14767643941971291
688 14918133510937552
689 15069935624859024
690 15223059809525880
691 15377515645953708
692 15533312770623284
693 15690460875721038
694 15848969709380214
695 16008849075922725
696 16170108836101704
697 16332758907344752
698 16496809263997884
699 16662269937570174
700 16829151016979100
701 16997462648796590
702 17167215037495770
703 17338418445698415
704 17511083194423104
705 17685219663334080
706 17860838290990816
707 18037949575098288
708 18216564072757956
709 18396692400719454
710 18578345235632990
711 18761533314302457
712 18946267433939256
713 19132558452416832
714 19320417288525924
715 19509854922230530
716 19700882394924588
717 19893510809689374
718 20087751331551618
719 20283615187742339
720 20481113667956400
721 20680258124612784
722 20881059973115592
723 21083530692115764
724 21287681823773524
725 21493524974021550
726 21701071812828870
727 21910334074465485
728 22121323557767720
729 22334052126404304
730 22548531709143180
731 22764774300119046
732 22982791959101628
733 23202596811764686
734 23424201049955754
735 23647616931966615
736 23872856782804512
737 24099932994464096
738 24328858026200112
739 24559644404800824
740 24792304724862180
741 25026851649062718
742 25263297908439214
743 25501656302663073
744 25741939700317464
745 25984161039175200
746 26228333326477364
747 26474469639212682
748 26722583124397644
749 26972686999357374
750 27224794552007250
751 27478919141135275
752 27735074196685200
753 27993273220040400
754 28253529784308504
755 28515857534606780
756 28780270188348276
757 29046781535528718
758 29315405439014166
759 29586155834829429
760 29859046732447240
761 30134092215078192
762 30411306439961436
763 30690703638656142
764 30972298117333724
765 31256104257070830
766 31542136514143098
767 31830409420319679
768 32120937583158528
769 32413735686302464
770 32708818489776000
771 33006200830282944
772 33305897621504772
773 33607923854399774
774 33912294597502974
775 34219024997226825
776 34528130278162680
777 34839625743383040
778 35153526774744580
779 35469848833191954
780 35788607459062380
781 36109818272391006
782 36433496973217058
783 36759659341890771
784 37088321239381104
785 37419498607584240
786 37753207469632872
787 38089463930206276
788 38428284175841172
789 38769684475243374
790 39113681179600230
791 39460290722893853
792 39809529622215144
793 40161414478078608
794 40515961974737964
795 40873188880502550
796 41233112048054524
797 41595748414766862
798 41961115003022154
799 42329228920532199
800 42700107360658400
801 43073767602732960
802 43450227012380880
803 43829503041842760
804 44211613230298404
805 44596575204191230
806 44984406677553486
807 45375125452332273
808 45768749418716376
809 46165296555463904
810 46564784930230740
811 46967232699899802
812 47372658110911116
813 47781079499592702
814 48192515292492274
815 48606984006709755
816 49024504250230608
817 49445094722259984
818 49868774213557688
819 50295561606773964
820 50725475876786100
821 51158536091035854
822 51594761409867702
823 52034171086867909
824 52476784469204424
825 52922620997967600
826 53371700208511740
827 53824041730797470
828 54279665289734940
829 54738590705527854
830 55200837894018330
831 55666426867032591
832 56135377732727488
833 56607710695937856
834 57083446058524704
835 57562604219724240
836 58045205676497732
837 58531271023882206
838 59020820955341982
839 59513876263121049
840 60010457838596280
841 60510586672631488
842 61014283855932324
843 61521570579402018
844 62032468134497964
845 62546997913589150
846 63065181410314434
847 63587040219941667
848 64112596039727664
849 64641870669279024
850 65174886010913800
851 65711664070024020
852 66252226955439060
853 66796596879789870
854 67344796159874054
855 67896847217021805
856 68452772577462696
857 69012594872693328
858 69576336839845836
859 70144021322057254
860 70715671268839740
861 71291309736451662
862 71870959888269546
863 72454644995160887
864 73042388435857824
865 73634213697331680
866 74230144375168368
867 74830204173944664
868 75434416907605348
869 76042806499841214
870 76655396984467950
871 77272212505805889
872 77893277319060632
873 78518615790704544
874 79148252398859124
875 79782211733678250
876 80420518497732300
877 81063197506393150
878 81710273688220050
879 82361772085346379
880 83017717853867280
881 83678136264228176
882 84343052701614168
883 85012492666340316
884 85686481774242804
885 86365045757070990
886 87048210462880342
887 87736001856426261
888 88428446019558792
889 89125569151618224
890 89827397569831580
891 90533957709709998
892 91245276125447004
893 91961379490317678
894 92682294597078714
895 93408048358369375
896 94138667807113344
897 94874180096921472
898 95614612502495424
899 96359992420032224
900 97110347367629700
901 97865704985692830
902 98626093037340990
903 99391539408816105
904 100162072109891704
905 100937719274282880
906 101718509160057156
907 102504470150046258
908 103295630752258796
909 104092019600293854
910 104893665453755490
911 105700597198668147
912 106512843847892976
913 107330434541545072
914 108153398547411624
915 108981765261370980
916 109815564207812628
917 110654825040058094
918 111499577540782758
919 112349851622438589
920 113205677327677800
921 114067084829777424
922 114934104433064812
923 115806766573344054
924 116685101818323324
925 117569140868043150
926 118458914555305610
927 119354453846104455
928 120255789840056160
929 121162953770831904
930 122075977006590480
931 122994891050412136
932 123919727540733348
933 124850518251782526
934 125787295094016654
935 126730090114558865
936 127678935497636952
937 128633863565022816
938 129594906776472852
939 130562097730169274
940 131535469163162380
941 132515053951813758
942 133500885112240434
943 134492995800759963
944 135491419314336464
945 136496189091027600
946 137507338710432504
947 138524901894140652
948 139548912506181684
949 140579404553476174
950 141616412186287350
951 142659969698673765
952 143710111528942920
953 144766872260105840
954 145830286620332604
955 146900389483408830
956 147977215869193116
957 149060800944075438
958 150151180021436506
959 151248388562108079
960 152352462174834240
961 153463436616733632
962 154581347793762656
963 155706231761179632
964 156838124724009924
965 157977063037512030
966 159123083207644638
967 160276221891534649
968 161436515897946168
969 162604002187750464
970 163778717874396900
971 164960700224384834
972 166149986657736492
973 167346614748470814
974 168550622225078274
975 169762046970996675
976 170980927025087920
977 172207300582115760
978 173441205993224520
979 174682681766418804
980 175931766567044180
981 177188499218268846
982 178452918701566278
983 179725064157198861
984 181004974884702504
985 182292690343372240
986 183588250152748812
987 184891694093106246
988 186203062105940412
989 187522394294458574
990 188849730924069930
991 190185112422877143
992 191528579382168864
993 192880172556913248
994 194239932866252464
995 195607901393998200
996 196984119389128164
997 198368628266283582
998 199761469606267694
999 201162685156545249
1000 202572316831743000