4 1
5 15
6 90
7 357
8 1107
9 2907
10 6765
11 14355
12 28314
13 52624
14 93093
15 157950
16 258570
17 410346
18 633726
19 955434
20 1409895
21 2040885
22 2903428
23 4065963
24 5612805
25 7646925
26 10293075
27 13701285
28 18050760
29 23554206
30 30462615
31 39070540
32 49721892
33 62816292
34 78816012
35 98253540
36 121739805
37 149973099
38 183748734
39 223969473
40 271656775
41 327962895
42 394183881
43 471773511
44 562358214
45 667753020
46 789978585
47 931279338
48 1094142798
49 1281320110
50 1495847850
51 1741071150
52 2020668195
53 2338676145
54 2699518536
55 3108034215
56 3569507865
57 4089702177
58 4674891727
59 5331898617
60 6068129940
61 6891617130
62 7811057259
63 8835856344
64 9976174728
65 11242974600
66 12648069720
67 14204177416
68 15924972921
69 17825146119
70 19920460770
71 22227816285
72 24765312123
73 27552314883
74 30609528165
75 33959065275
76 37624524850
77 41631069480
78 46005507405
79 50776377366
80 55974036690
81 61630752690
82 67780797462
83 74460546162
84 81708578847
85 89565785965
86 98075477580
87 107283496419
88 117238334829
89 127991255733
90 139596417675
91 152111004045
92 165595356576
93 180113113206
94 195731350399
95 212520730020
96 230555650860
97 249914404908
98 270679338468
99 292937018220
100 316778402325
101 342299016675
102 369599136390
103 398783972665
104 429963865071
105 463254479415
106 498777011265
107 536658395247
108 577031520222
109 620035450452
110 665815652865
111 714524230530
112 766320162454
113 821369549814
114 879845868738
115 941930229750
116 1007811643995
117 1077687296361
118 1151762825616
119 1230252611679
120 1313380070145
121 1401377954185
122 1494488663943
123 1592964563553
124 1697068305900
125 1807073165250
126 1923263377875
127 2045934490800
128 2175393718800
129 2311960309776
130 2455965918640
131 2607754989840
132 2767685148657
133 2936127601407
134 3113467544682
135 3300104583765
136 3496453160355
137 3702942989739
138 3920019507549
139 4148144326243
140 4387795701450
141 4639469008320
142 4903677228021
143 5180951444526
144 5471841351834
145 5776915771770
146 6096763182510
147 6431992257978
148 6783232418263
149 7151134391205
150 7536370785300
151 7939636674075
152 8361650192085
153 8803153142685
154 9264911617731
155 9747716629365
156 10252384754040
157 10779758788942
158 11330708420967
159 11906130908412
160 12506951775540
161 13134125520180
162 13788636334524
163 14471498839284
164 15183758831373
165 15926494045275
166 16700814928270
167 17507865429681
168 18348823804311
169 19224903430239
170 20137353641145
171 21087460573335
172 22076548027638
173 23105978346348
174 24177153305385
175 25291515021850
176 26450546877150
177 27655774455870
178 28908766500570
179 30211135882686
180 31564540589715
181 32970684728865
182 34431319547352
183 35948244469527
184 37523308151017
185 39158409550065
186 40855499016255
187 42616579396809
188 44443707160644
189 46338993540378
190 48304605692475
191 50342767875720
192 52455762648216
193 54645932083096
194 56915679003144
195 59267468234520
196 61703827879785
197 64227350610423
198 66840694979058
199 69546586751565
200 72347820259275
201 75247259771475
202 78247840888405
203 81352571954955
204 84564535495266
205 87886889668440
206 91322869745565
207 94875789608262
208 98549043268962
209 102346106413122
210 106270537963590
211 110325981667330
212 114516167704719
213 118844914321629
214 123316129484508
215 127933812558675
216 132702056010045
217 137625047130501
218 142707069787131
219 147952506195549
220 153365838717520
221 158951651683110
222 164714633237583
223 170659577213268
224 176791385026620
225 183115067600700
226 189635747313300
227 196358659970940
228 203289156808965
229 210432706517971
230 217794897296790
231 225381438932265
232 233198164906047
233 241251034528647
234 249546135100977
235 258089684103615
236 266888031414030
237 275947661552004
238 285275195953489
239 294877395273138
240 304761161715750
241 314933541396870
242 325401726732786
243 336173058860166
244 347255030085579
245 358655286365145
246 370381629814560
247 382442021249743
248 394844582758353
249 407597600302425
250 420709526352375
251 434188982552625
252 448044762419100
253 462285834068850
254 476921342982051
255 491960614796640
256 507413158135840
257 523288667468832
258 539597026004832
259 556348308620832
260 573552784823265
261 591220921743855
262 609363387169914
263 627991052609349
264 647114996390643
265 666746506798075
266 686897085242445
267 707578449467571
268 728802536792826
269 750581507391984
270 772927747608645
271 795853873308510
272 819372733268778
273 843497412604938
274 868241236235230
275 893617772383050
276 919640836117575
277 946324492932885
278 973683062365860
279 1001731121653131
280 1030483509427365
281 1059955329453165
282 1090161954402867
283 1121119029672517
284 1152842477238312
285 1185348499553790
286 1218653583488055
287 1252774504305324
288 1287728329686084
289 1323532423790148
290 1360204451361900
291 1397762381878020
292 1436224493737981
293 1475609378497611
294 1515935945146014
295 1557223424426145
296 1599491373199335
297 1642759678854063
298 1687048563759273
299 1732378589762535
300 1778770662733350
301 1826246037151900
302 1874826320743545
303 1924533479159370
304 1975389840703086
305 2027418101104590
306 2080641328340490
307 2135082967501902
308 2190766845709827
309 2247717177078417
310 2305958567726440
311 2365516020837255
312 2426414941767609
313 2488681143205569
314 2552340850377903
315 2617420706307225
316 2683947777119220
317 2751949557400266
318 2821453975605771
319 2892489399519544
320 2965084641764520
321 3039268965365160
322 3115072089361848
323 3192524194477608
324 3271655928837465
325 3352498413740775
326 3435083249486850
327 3519442521254205
328 3605608805033755
329 3693615173616291
330 3783495202634565
331 3875282976660315
332 3969013095356562
333 4064720679685512
334 4162441378172397
335 4262211373225590
336 4364067387513330
337 4468046690397394
338 4574187104424054
339 4682527011872658
340 4793105361362175
341 4905961674516045
342 5021136052685676
343 5138669183732931
344 5258602348871949
345 5380977429570645
346 5505836914512235
347 5633223906617133
348 5763182130125568
349 5895755937741270
350 6030990317836575
351 6168930901719300
352 6309623970961740
353 6453116464792140
354 6599455987548996
355 6748690816198540
356 6900869907915765
357 7056042907729347
358 7214260156230822
359 7375572697348377
360 7540032286185615
361 7707691396925655
362 7878603230800929
363 8052821724129039
364 8230401556415038
365 8411398158520500
366 8595867720899745
367 8783867201903586
368 8975454336150966
369 9170687642968854
370 9369626434900770
371 9572330826284310
372 9778861741898043
373 9989280925678153
374 10203650949505200
375 10422035222061375
376 10644497997758625
377 10871104385738025
378 11101920358940775
379 11337012763251201
380 11576449326712140
381 11820298668813090
382 12068630309851507
383 12321514680367632
384 12579023130653232
385 12841227940334640
386 13108202328030480
387 13380020461084464
388 13656757465373649
389 13938489435192543
390 14225293443213450
391 14517247550523445
392 14814430816738371
393 15116923310194251
394 15424806118216509
395 15738161357467395
396 16057072184372010
397 16381622805623328
398 16711898488766613
399 17047985572863630
400 17389971479237050
401 17737944722295450
402 18091994920439310
403 18452212807048410
404 18818690241551031
405 19191520220575365
406 19570796889183540
407 19956615552188667
408 20349072685555317
409 20748265947883837
410 21154294191978915
411 21567257476502805
412 21987257077713624
413 22414395501289134
414 22848776494236423
415 23290505056887900
416 23739687454984020
417 24196431231843156
418 24660845220619036
419 25133039556646164
420 25613125689873645
421 26101216397387835
422 26597425796024238
423 27101869355069073
424 27614663909050935
425 28135927670622975
426 28665780243536025
427 29204342635703095
428 29751737272355670
429 30308088009292236
430 30873520146219465
431 31448160440186490
432 32032137119112702
433 32625579895409502
434 33228619979696442
435 33841390094612190
436 34464024488720755
437 35096658950513409
438 35739430822506744
439 36392479015437303
440 37055944022553225
441 37729967934003345
442 38414694451324191
443 39110268902025321
444 39816838254273444
445 40534551131675770
446 41263557828163035
447 42004010322972648
448 42756062295732408
449 43519869141645240
450 44295587986775400
451 45083377703436600
452 45883398925682505
453 46695814064900055
454 47520787325506066
455 48358484720747565
456 49209074088606315
457 50072725107807987
458 50949609313936437
459 51839900115653547
460 52743772811025090
461 53661404603953080
462 54592974620715069
463 55538663926610854
464 56498655542717058
465 57473134462750050
466 58462287670037670
467 59466304154600226
468 60485374930341231
469 61519693052348349
470 62569453634305020
471 63634853866013235
472 64716093031027933
473 65813372524403493
474 66926895870552795
475 68056868741219325
476 69203498973562800
477 70366996588358790
478 71547573808312815
479 72745445076489396
480 73960827074856540
481 75193938742946140
482 76445001296630772
483 77714238247017372
484 79001875419458277
485 80308140972680115
486 81633265418031030
487 82977481638846729
488 84341024909935839
489 85724132917185063
490 87127045777284625
491 88550006057574495
492 89993258796011886
493 91457051521260516
494 92941634272902129
495 94447259621770770
496 95974182690410310
497 97522661173655718
498 99092955359338578
499 100685328149117350
500 102300045079432875
501 103937374342589625
502 105597586807963200
503 107280956043334575
504 108987758336351601
505 110718272716118265
506 112472780974912215
507 114251567690031057
508 116054920245767932
509 117883128855516882
510 119736486584008515
511 121615289369676480
512 123519836047155264
513 125450428369909824
514 127407371032997568
515 129390971695963200
516 131401541005866945
517 133439392620446671
518 135504843231414426
519 137598212587887909
520 139719823519957395
521 141870001962388635
522 144049076978462253
523 146257380783950163
524 148495248771229530
525 150763019533534800
526 153061034889348325
527 155389639906930110
528 157749182928987210
529 160140015597483306
530 162562492878588990
531 165016973087773290
532 167503817915036967
533 170023392450288117
534 172576065208860612
535 175162208157175915
536 177782196738548805
537 180436409899137549
538 183125230114039059
539 185849043413529573
540 188608239409451400
541 191403211321746270
542 194234356005135831
543 197102073975949836
544 200006769439102564
545 202948850315218020
546 205928728267904460
547 208946818731178788
548 212003540937041373
549 215099317943201835
550 218234576660956350
551 221409747883217025
552 224625266312693895
553 227881570590230095
554 231179103323290761
555 234518311114606215
556 237899644590969990
557 241323558432192252
558 244790511400209177
559 248300966368348842
560 251855390350754190
561 255454254531963630
562 259098034296649834
563 262787209259517294
564 266522263295359203
565 270303684569274225
566 274131965567043720
567 278007603125669991
568 281931098464076121
569 285902957213967969
570 289923689450858895
571 293993809725257785
572 298113837094020948
573 302284295151868458
574 306505712063065515
575 310778620593269400
576 315103558141542600
577 319481066772532680
578 323911693248819480
579 328395989063430216
580 332934510472523065
581 337527818528239815
582 342176479111728162
583 346881062966334237
584 351642145730965947
585 356460307973627715
586 361336135225127205
587 366270218012954619
588 371263151895335154
589 376315537495455208
590 381427980535862925
591 386601091873043670
592 391835487532171026
593 397131788742033906
594 402490621970140374
595 407912618957998770
596 413398416756576735
597 418948657761938733
598 424563989751062668
599 430245065917836195
600 435992544909233325
601 441807090861671925
602 447689373437552715
603 453640067861980365
604 459659854959667296
605 465749421192020790
606 471909458694414015
607 478140665313641572
608 484443744645560172
609 490819406072915052
610 497268364803352740
611 503791341907620780
612 510389064357955029
613 517062265066655139
614 523811682924848838
615 530638062841445625
616 537542155782280495
617 544524718809448311
618 551586515120829441
619 558728314089807279
620 565950891305178270
621 573255028611255060
622 580641514148163393
623 588111142392333378
624 595664714197185750
625 603303036834013750
626 611026924033061250
627 618837196024797750
628 626734679581390875
629 634720208058377001
630 642794621436530640
631 650958766363933215
632 659213496198241857
633 667559671049158857
634 675998157821102407
635 684529830256079265
636 693155568976759980
637 701876261529757314
638 710692802429108499
639 719606093199961968
640 728617042422469200
641 737726565775882320
642 746935586082858096
643 756245033353968976
644 765655844832421809
645 775168965038984895
646 784785345817124010
647 794505946378348053
648 804331733347764963
649 814263680809848555
650 824302770354416925
651 834449991122823075
652 844706339854358410
653 855072820932869760
654 865550446433590581
655 876140236170186990
656 886843217742019290
657 897660426581619642
658 908592906002386542
659 919641707246496762
660 930807889533035415
661 942092520106344805
662 953496674284592724
663 965021435508560859
664 976667895390653973
665 988437153764130525
666 1000330318732555395
667 1012348506719475381
668 1024492842518318136
669 1036764459342515214
670 1049164498875849895
671 1061694111323030460
672 1074354455460489588
673 1087146698687410548
674 1100072017076980860
675 1113131595427874100
676 1126326627315960525
677 1139658315146247195
678 1153127870205048270
679 1166736512712386161
680 1180485471874624215
681 1194375985937331615
682 1208409302238381177
683 1222586677261280727
684 1236909376688738742
685 1251378675456464940
686 1265995857807206505
687 1280762217345020634
688 1295679057089784094
689 1310747689531940478
690 1325969436687485850
691 1341345630153193470
692 1356877611162078291
693 1372566730639101921
694 1388414349257118744
695 1404421837493063895
696 1420590575684383785
697 1436921954085709873
698 1453417372925776383
699 1470078242464582665
700 1486905983050800900
701 1503902025179429850
702 1521067809549695355
703 1538404787123198280
704 1555914419182310616
705 1573598177388820440
706 1591457543842826440
707 1609494011141882712
708 1627709082440394537
709 1646104271509265847
710 1664681102795799090
711 1683441111483848205
712 1702385843554225419
713 1721516855845362579
714 1740835716114227733
715 1760344003097497675
716 1780043306572987170
717 1799935227421335576
718 1820021377687951581
719 1840303380645216774
720 1860782870854948770
721 1881461494231124610
722 1902340908102865158
723 1923422781277681218
724 1944708794104982095
725 1966200638539847325
726 1987900018207062300
727 2009808648465418515
728 2031928256472279165
729 2054260581248410821
730 2076807373743081915
731 2099570396899428765
732 2122551425720089872
733 2145752247333109222
734 2169174661058109327
735 2192820478472734740
736 2216691523479366780
737 2240789632372110204
738 2265116653904052564
739 2289674449354796988
740 2314464892598269125
741 2339489870170798995
742 2364751281339478486
743 2390251038170795241
744 2415991065599543679
745 2441973301498013895
746 2468199696745459185
747 2494672215297842943
748 2521392834257865678
749 2548363543945272900
750 2575586347967444625
751 2603063263290267250
752 2630796320309288550
753 2658787562921156550
754 2687039048595343026
755 2715552848446152390
756 2744331047305016715
757 2773375743793077657
758 2802689050394056032
759 2832273093527409807
760 2862130013621781265
761 2892261965188734105
762 2922671116896781239
763 2953359651645704049
764 2984329766641163868
765 3015583673469606450
766 3047123598173460195
767 3078951781326628896
768 3111070478110279776
769 3143481958388927584
770 3176188506786815520
771 3209192422764593760
772 3242496020696296353
773 3276101629946617263
774 3310011594948486330
775 3344228275280945925
776 3378754045747329075
777 3413591296453739835
778 3448742432887836685
779 3484209875997919731
780 3519996062272322490
781 3556103443819109040
782 3592534488446077317
783 3629291679741069342
784 3666377517152589162
785 3703794516070729290
786 3741545207908406430
787 3779632140182907274
788 3818057876597745159
789 3856824997124828373
790 3895936098086940900
791 3935393792240536395
792 3975200708858846181
793 4015359493815302061
794 4055872809667274739
795 4096743335740128645
796 4137973768211593960
797 4179566820196456638
798 4221525221831567223
799 4263851720361169260
800 4306549080222548100
801 4349620083132000900
802 4393067528171128620
803 4436894231873450820
804 4481103028311344061
805 4525696769183304715
806 4570678323901536990
807 4616050579679866977
808 4661816441621983527
809 4707978832810006767
810 4754540694393385065
811 4801504985678121255
812 4848874684216328934
813 4896652785896119644
814 4944842305031821753
815 4993446274454531850
816 5042467745602999470
817 5091909788614845966
818 5141775492418118346
819 5192067964823178894
820 5242790332614931395
821 5293945741645384785
822 5345537356926555048
823 5397568362723706183
824 5450041962648931065
825 5502961379755073025
826 5556329856629988975
827 5610150655491154905
828 5664427058280614580
829 5719162366760272266
830 5774359902607530315
831 5830023007511272440
832 5886155043268193512
833 5942759391879476712
834 5999839455647818872
835 6057398657274804840
836 6115440439958631705
837 6173968267492183719
838 6232985624361458754
839 6292496015844347133
840 6352502968109763675
841 6413010028317133795
842 6474020764716234501
843 6535538766747391131
844 6597567645142030674
845 6660111032023592520
846 6723172581008797485
847 6786755967309275958
848 6850864887833556018
849 6915503061289412370
850 6980674228286576950
851 7046382151439812050
852 7112630615472346815
853 7179423427319677965
854 7246764416233735596
855 7314657433887414915
856 7383106354479474765
857 7452115074839803797
858 7521687514535055147
859 7591827615974650477
860 7662539344517154240
861 7733826688577019030
862 7805693659731702879
863 7878144292829159364
864 7951182646095701388
865 8024812801244239500
866 8099038863582895620
867 8173864962123993036
868 8249295249693423541
869 8325333903040392579
870 8401985122947543270
871 8479253134341460185
872 8557142186403553743
873 8635656552681326103
874 8714800531200019425
875 8794578444574647375
876 8874994640122410750
877 8956053489975498100
878 9037759391194272225
879 9120116765880843426
880 9203130061293030390
881 9286803749958709590
882 9371142329790554082
883 9456150324201162582
884 9541832282218579707
885 9628192778602208265
886 9715236413959114480
887 9802967814860727039
888 9891391633959930849
889 9980512550108556393
890 10070335268475265575
891 10160864520663834945
892 10252105064831837196
893 10344061685809721826
894 10436739195220295859
895 10530142431598605520
896 10624276260512219760
897 10719145574681916528
898 10814755294102772688
899 10911110366165658480
900 11008215765779137425
901 11106076495491772575
902 11204697585614840010
903 11304084094345450485
904 11404241107890080131
905 11505173740588511115
906 11606887135038183165
907 11709386462218956867
908 11812676921618289642
909 11916763741356825312
910 12021652178314398165
911 12127347518256452430
912 12233855075960878074
913 12341180195345263834
914 12449328249594568398
915 12558304641289210650
916 12668114802533579895
917 12778764195084966981
918 12890258310482917236
919 13002602670179006139
920 13115802825667038645
921 13229864358613673085
922 13344792880989470563
923 13460594035200370773
924 13577273494219595160
925 13694836961719978350
926 13813290172206728775
927 13932638891150619420
928 14052888915121609620
929 14174046071922898836
930 14296116220725413340
931 14419105252202726740
932 14543019088666415277
933 14667863684201848827
934 14793645024804418542
935 14920369128516202065
936 15048042045563067255
937 15176669858492215359
938 15306258682310164569
939 15436814664621174903
940 15568343985766115350
941 15700852858961774220
942 15834347530440613641
943 15968834279590969146
944 16104319419097695294
945 16240809295083258270
946 16378310287249276410
947 16516828809018509598
948 16656371307677298483
949 16796944264518454465
950 16938554194984601400
951 17081207648811969975
952 17224911210174645705
953 17369671497829271505
954 17515495165260205791
955 17662388900825137065
956 17810359427901155940
957 17959413505031285562
958 18109557926071471387
959 18260799520338031272
960 18413145152755566840
961 18566601724005337080
962 18721176170674095144
963 18876875465403389304
964 19033706617039329033
965 19191676670782817175
966 19350792708340249170
967 19511061848074680301
968 19672491245157461931
969 19835088091720347699
970 19998859617008070645
971 20163813087531392235
972 20329955807220624258
973 20497295117579624568
974 20665838397840267645
975 20835593065117390950
976 21006566574564218050
977 21178766419528259490
978 21352200131707692390
979 21526875281308219746
980 21702799477200410415
981 21879980367077520765
982 22058425637613798972
983 22238143014623272947
984 22419140263219022877
985 22601425187972939365
986 22785005633075968155
987 22969889482498842429
988 23156084660153303664
989 23343599130053812038
990 23532440896479747375
991 23722618004138101620
992 23914138538326663836
993 24107010625097698716
994 24301242431422119604
995 24496842165354157020
996 24693818076196523685
997 24892178454666077043
998 25091931633059980278
999 25293085985422362825
1000 25495649927711481375