4 1
5 4
6 11
7 29
8 76
9 196
10 487
11 1148
12 2552
13 5353
14 10636
15 20120
16 36425
17 63415
18 106630
19 173821
20 275603
21 426242
22 644593
23 955207
24 1389626
25 1987886
26 2800249
27 3889186
28 5331634
29 7221551
30 9672794
31 12822346
32 16833919
33 21901961
34 28256096
35 36166027
36 45946933
37 57965392
38 72645863
39 90477761
40 112023160
41 137925160
42 168916955
43 205831640
44 249612796
45 301325893
46 362170552
47 433493708
48 516803717
49 613785451
50 726316426
51 856484009
52 1006603751
53 1179238894
54 1377221101
55 1603672459
56 1862028806
57 2156064434
58 2489918221
59 2868121246
60 3295625942
61 3777836843
62 4320642982
63 4930451998
64 5614226011
65 6379519325
66 7234518020
67 8188081495
68 9249786025
69 10429970396
70 11739783683
71 13191235237
72 14797246948
73 16571707852
74 18529531151
75 20686713716
76 23060398144
77 25668937441
78 28531962404
79 31670451776
80 35106805249
81 38864919391
82 42970266574
83 47449976981
84 52332923771
85 57649811482
86 63433267753
87 69717938447
88 76540586258
89 83940192886
90 91958064865
91 100637943130
92 110026116410
93 120171538535
94 131125949746
95 142944002098
96 155683389047
97 169404979313
98 184172955112
99 200054954851
100 217122220381
101 235449748904
102 255116449631
103 276205305289
104 298803538576
105 323002783664
106 348899262851
107 376593968464
108 406192850116
109 437807007421
110 471552888272
111 507552492788
112 545933583037
113 586829898643
114 630381378386
115 676734387905
116 726041953615
117 778464002950
118 834167611045
119 893327253971
120 956125068638
121 1022751119482
122 1093403672053
123 1168289473622
124 1247624040926
125 1331631955171
126 1420547164414
127 1514613293446
128 1614083961299
129 1719223106501
130 1830305320204
131 1947616187311
132 2071452635729
133 2202123293876
134 2339948856571
135 2485262459437
136 2638410061948
137 2799750839252
138 2969657582903
139 3148517110636
140 3336730685320
141 3534714443225
142 3742899831740
143 3961734056680
144 4191680539321
145 4433219383303
146 4686847851542
147 4953080853293
148 5232451441507
149 5525511320626
150 5832831364961
151 6155002147799
152 6492634481386
153 6846359967934
154 7216831561801
155 7604724142994
156 8010735102146
157 8435584937119
158 8880017861386
159 9344802424346
160 9830732143727
161 10338626150233
162 10869329844592
163 11423715567163
164 12002683280261
165 12607161263360
166 13238106821335
167 13896507005905
168 14583379350440
169 15299772618296
170 16046767564843
171 16825477713352
172 17637050144908
173 18482666302517
174 19363542809576
175 20280932302876
176 21236124280309
177 22230445963451
178 23265263175194
179 24341981232601
180 25462045855159
181 26626944088606
182 27838205244509
183 29097401855771
184 30406150648246
185 31766113528642
186 33178998588893
187 34646561127182
188 36170604685798
189 37752982106011
190 39395596600150
191 41100402841070
192 42869408069195
193 44704673217325
194 46608314053396
195 48582502341383
196 50629467020537
197 52751495403148
198 54950934391027
199 57230191710901
200 59591737168916
201 62038103924444
202 64571889783391
203 67195758511204
204 69912441165776
205 72724737450449
206 75635517087316
207 78647721211024
208 81764363783281
209 84988533028271
210 88323392889182
211 91772184506053
212 95338227715147
213 99024922570058
214 102835750884761
215 106774277798815
216 110844153364930
217 115049114159110
218 119392984913585
219 123879680172746
220 128513205972298
221 133297661541847
222 138237241031138
223 143336235260162
224 148599033493351
225 154030125238081
226 159634102067704
227 165415659469331
228 171379598716589
229 177530828767576
230 183874368188239
231 190415347101401
232 197159009161664
233 204110713556416
234 211275937033171
235 218660275953472
236 226269448373588
237 234109296152237
238 242185787085568
239 250505017069636
240 259073212290605
241 267896731442915
242 276982067975650
243 286335852367345
244 295964854429471
245 305875985638838
246 316076301499157
247 326573003932003
248 337373443697422
249 348485122844426
250 359915697191621
251 371672978838214
252 383764938705646
253 396199709110099
254 408985586366126
255 422131033421654
256 435644682524611
257 449535337921429
258 463811978587676
259 478483760991071
260 493560021887137
261 509050281147748
262 524964244622827
263 541311807035453
264 558103054910636
265 575348269538020
266 593057929968775
267 611242716046940
268 629913511475480
269 649081406917321
270 668757703131628
271 688953914145592
272 709681770461993
273 730953222302807
274 752780442889126
275 775175831757661
276 798152018114099
277 821721864223586
278 845898468838609
279 870695170664551
280 896125551863194
281 922203441594446
282 948942919596569
283 976358319805186
284 1004464234011346
285 1033275515558927
286 1062807283081658
287 1093074924280042
288 1124094099738463
289 1155880746782761
290 1188451083378560
291 1221821612070635
292 1256009123963605
293 1291030702744240
294 1326903728745671
295 1363645883053793
296 1401275151656152
297 1439809829633608
298 1479268525395067
299 1519670164955576
300 1561033996258076
301 1603379593539109
302 1646726861738776
303 1691096040955244
304 1736507710944101
305 1782982795662859
306 1830542567860906
307 1879208653715209
308 1929003037512071
309 1979948066375246
310 2032066455040717
311 2085381290678443
312 2139916037761382
313 2195694542982098
314 2252741040217261
315 2311080155540350
316 2370736912282870
317 2431736736144395
318 2494105460351750
319 2557869330867646
320 2623055011649083
321 2689689589955837
322 2757800581709348
323 2827415936902327
324 2898564045059401
325 2971273740749116
326 3045574309147619
327 3121495491654341
328 3199067491560004
329 3278320979767276
330 3359287100564399
331 3441997477452116
332 3526484219024224
333 3612779924902081
334 3700917691723396
335 3790931119185632
336 3882854316144353
337 3976721906766847
338 4072569036741358
339 4170431379542261
340 4270345142751515
341 4372347074436730
342 4476474469586185
343 4582765176601135
344 4691257603845746
345 4801990726254998
346 4915004092000897
347 5030337829217338
348 5148032652783962
349 5268129871169351
350 5390671393333906
351 5515699735692754
352 5643258029139031
353 5773390026127889
354 5906140107821576
355 6041553291295939
356 6179675236808701
357 6320552255129864
358 6464231314934591
359 6610760050258921
360 6760186768018672
361 6912560455591888
362 7067930788465187
363 7226348137944368
364 7387863578929636
365 7552528897755805
366 7720396600097840
367 7891519918942100
368 8065952822623645
369 8243750022929971
370 8424966983271538
371 8609659926919457
372 8797885845310703
373 8989702506421222
374 9185168463207301
375 9384343062115571
376 9587286451662014
377 9794059591080346
378 10004724259040149
379 10219343062435126
380 10437979445241854
381 10660697697449411
382 10887562964060254
383 11118641254162726
384 11353999450075571
385 11593705316564837
386 11837827510133548
387 12086435588384527
388 12339600019456753
389 12597392191535636
390 12859884422437595
391 13127149969269325
392 13399263038162140
393 13676298794081780
394 13958333370714071
395 14245443880426828
396 14537708424308392
397 14835206102283193
398 15138017023304732
399 15446222315626376
400 15759904137150361
401 16079145685855399
402 16404031210303286
403 16734646020224909
404 17071076497186051
405 17413410105333394
406 17761735402221121
407 18116142049718519
408 18476720824998986
409 18843563631610846
410 19216763510630377
411 19596414651897458
412 19982612405334242
413 20375453292347263
414 20775035017313386
415 21181456479150010
416 21594817782969935
417 22015220251821305
418 22442766438513040
419 22877560137526171
420 23319706397011493
421 23769311530873952
422 24226483130944183
423 24691330079237617
424 25163962560301576
425 25644492073650776
426 26133031446291659
427 26629694845335976
428 27134597790704044
429 27647857167918101
430 28169591240986184
431 28699919665376956
432 29238963501085909
433 29786845225793371
434 30343688748114746
435 30909619420943417
436 31484764054886743
437 32069250931795582
438 32663209818387773
439 33266771979966011
440 33880070194230550
441 34503238765187170
442 35136413537150845
443 35779731908845550
444 36433332847600646
445 37097356903644283
446 37771946224494262
447 38457244569446798
448 39153397324163627
449 39860551515357901
450 40578855825579316
451 41308460608098919
452 42049517901894041
453 42802181446733804
454 43566606698365651
455 44342950843803349
456 45131372816716916
457 45932033312924924
458 46745094805989631
459 47570721562915396
460 48409079659950832
461 49260336998495153
462 50124663321109172
463 51002230227631408
464 51893211191399761
465 52797781575579215
466 53716118649596030
467 54648401605678885
468 55594811575507435
469 56555531646968746
470 57530746881022073
471 58520644328672447
472 59525413048053538
473 60545244121620262
474 61580330673451601
475 62630867886664106
476 63697053020936554
477 64779085430146231
478 65877166580117314
479 66991500066481826
480 68122291632653639
481 69269749187916001
482 70434082825623064
483 71615504841515891
484 72814229752153421
485 74030474313458872
486 75264457539382063
487 76516400720678137
488 77786527443803168
489 79075063609927136
490 80382237454064755
491 81708279564324640
492 83053422901277300
493 84417902817442445
494 85801957076896096
495 87205825874997988
496 88629751858239757
497 90073980144214403
498 91538758341707522
499 93024336570910801
500 94530967483758271
501 96058906284385814
502 97608410749714421
503 99179741250157699
504 100773160770454126
505 102388934930624554
506 104027332007055461
507 105688622953708454
508 107373081423456526
509 109080983789547571
510 110812609167195662
511 112568239435300598
512 114348159258296227
513 116152656108128053
514 117982020286360636
515 119836544946415295
516 121716526115938625
517 123622262719302340
518 125554056600234955
519 127512212544585821
520 129497038303222028
521 131508844615058692
522 133547945230223143
523 135614656933353532
524 137709299567032376
525 139832196055355561
526 141983672427637324
527 144164057842251736
528 146373684610611209
529 148612888221282551
530 150882007364241094
531 153181383955263421
532 155511363160459219
533 157872293420942786
534 160264526477644721
535 162688417396264327
536 165144324592363258
537 167632609856600942
538 170153638380112313
539 172707778780028386
540 175295403125140210
541 177916886961706735
542 180572609339407130
543 183262952837438090
544 185988303590756671
545 188749051316469193
546 191545589340366752
547 194378314623607883
548 197247627789548917
549 200153933150722576
550 203097638735965351
551 206079156317694209
552 209098901439333176
553 212157293442890344
554 215254755496685851
555 218391714623231384
556 221568601727261756
557 224785851623919109
558 228043903067090296
559 231343198777897996
560 234684185473346117
561 238067313895120043
562 241493038838542282
563 244961819181684073
564 248474117914633511
565 252030402168920750
566 255631143247100845
567 259276816652494795
568 262967902119089350
569 266704883641596146
570 270488249505670733
571 274318492318292062
572 278196109038302998
573 282121601007112427
574 286095473979559526
575 290118238154940766
576 294190408208200219
577 298312503321283741
578 302485047214657604
579 306708568178992151
580 310983599107011049
581 315310677525506716
582 319690345627522499
583 324123150304702181
584 328609643179807396
585 333150380639403532
586 337745923866714703
587 342396838874648372
588 347103696538990208
589 351867072631769761
590 356687547854797540
591 361565707873374080
592 366502143350171585
593 371497449979288735
594 376552228520479246
595 381667084833554773
596 386842629912962747
597 392079479922539738
598 397378256230440937
599 402739585444246351
600 408164099446244306
601 413652435428892854
602 419205235930459681
603 424823148870841114
604 430506827587560826
605 436256930871948839
606 442074123005501426
607 447959073796422514
608 453912458616347191
609 459934958437247921
610 466027259868524072
611 472190055194275363
612 478424042410759837
613 484729925264036968
614 491108413287796511
615 497560221841373705
616 504086072147951440
617 510686691332950000
618 517362812462604995
619 524115174582734096
620 530944522757693188
621 537851608109522557
622 544837187857283728
623 551902025356587572
624 559046890139314301
625 566272557953525971
626 573579810803572114
627 580969436990389121
628 588442231151993999
629 595998994304173126
630 603640533881366629
631 611367663777749011
632 619181204388506654
633 627081982651312826
634 635070832088000821
635 643148592846435862
636 651316111742586398
637 659574242302795427
638 667923844806252478
639 676365786327666886
640 684900940780142995
641 693530188958257925
642 702254418581342540
643 711074524336966255
644 719991407924626321
645 729005978099642228
646 738119150717255867
647 747331848776938093
648 756645002466902332
649 766059549208825876
650 775576433702779511
651 785196607972366124
652 794921031410068936
653 804750670822810009
654 814686500477719676
655 824729502148117544
656 834880665159705721
657 845140986436974919
658 855511470549824086
659 865993129760394221
660 876586984070117027
661 887294061266979058
662 898115396973002017
663 909052034691939863
664 920105025857193386
665 931275429879942910
666 942564314197499785
667 953972754321877330
668 965501833888581890
669 977152644705624671
670 988926286802755018
671 1000823868480915802
672 1012846506361921583
673 1024995325438360217
674 1037271459123718576
675 1049676049302733051
676 1062210246381965509
677 1074875209340605376
678 1087672105781498519
679 1100602111982403601
680 1113666412947476584
681 1126866202458984056
682 1140202683129246059
683 1153677066452809096
684 1167290572858849996
685 1181044431763811317
686 1194939881624268968
687 1208978169990032732
688 1223160553557480373
689 1237488298223126011
690 1251962679137423450
691 1266584980758805145
692 1281356496907957495
693 1296278530822333150
694 1311352395210901021
695 1326579412309134683
696 1341960913934239862
697 1357498241540621698
698 1373192746275592477
699 1389045789035320526
700 1405058740521020966
701 1421232981295389019
702 1437569901839276566
703 1454070902608612654
704 1470737394091568651
705 1487570796865968749
706 1504572541656946516
707 1521744069394848199
708 1539086831273383481
709 1556602288808024396
710 1574291913894653107
711 1592157188868459253
712 1610199606563087572
713 1628420670370036508
714 1646821894298308511
715 1665404803034312740
716 1684170932002020880
717 1703121827423376785
718 1722259046378960660
719 1741584156868908496
720 1761098737874087473
721 1780804379417528047
722 1800702682626113438
723 1820795259792527237
724 1841083734437459851
725 1861569741372074506
726 1882254926760733529
727 1903140948183985631
728 1924229474701814914
729 1945522186917152326
730 1967020777039650289
731 1988726948949721226
732 2010642418262840714
733 2032768912394115991
734 2055108170623120546
735 2077661944158995522
736 2100431996205818663
737 2123420102028241537
738 2146628049017395768
739 2170057636757069011
740 2193710677090151405
741 2217588994185353240
742 2241694424604194575
743 2266028817368267545
744 2290594034026772096
745 2315391948724325888
746 2340424448269049107
747 2365693432200924928
748 2391200812860436372
749 2416948515457480301
750 2442938478140559296
751 2469172652066252164
752 2495653001468963821
753 2522381503730955299
754 2549360149452654626
755 2576590942523249329
756 2604075900191561311
757 2631817053137204854
758 2659816445542028501
759 2688076135161841571
760 2716598193398426062
761 2745384705371834698
762 2774437769992975877
763 2803759500036486278
764 2833352022213891886
765 2863217477247058195
766 2893358019941930350
767 2923775819262563990
768 2954473058405447555
769 2985451934874116821
770 3016714660554062428
771 3048263461787931167
772 3080100579451021793
773 3112228269027076132
774 3144648800684366251
775 3177364459352078461
776 3210377544796994924
777 3243690371700473636
778 3277305269735727559
779 3311224583645403676
780 3345450673319462744
781 3379985913873360521
782 3414832695726531244
783 3449993424681174136
784 3485470522001343721
785 3521266424492344727
786 3557383584580432358
787 3593824470392818717
788 3630591565837986163
789 3667687370686308386
790 3705114400650979985
791 3742875187469255335
792 3780972278983997530
793 3819408239225538190
794 3858185648493848921
795 3897307103441025218
796 3936775217154083602
797 3976592619238072783
798 4016761955899499642
799 4057285890030070826
800 4098167101290750751
801 4139408286196136809
802 4181012158199152576
803 4222981447776059819
804 4265318902511790101
805 4308027287185596784
806 4351109383857028231
807 4394567991952223009
808 4438405928350527896
809 4482626027471439496
810 4527231141361870267
811 4572224139783739768
812 4617607910301891932
813 4663385358372339173
814 4709559407430834136
815 4756132998981769900
816 4803109092687409445
817 4850490666457445195
818 4898280716538889450
819 4946482257606296521
820 4995098322852317383
821 5044131964078587662
822 5093586251786949773
823 5143464275271010027
824 5193769142708031526
825 5244503981251163666
826 5295671937122009069
827 5347276175703528766
828 5399319881633286454
829 5451806258897032651
830 5504738530922629574
831 5558119940674317566
832 5611953750747323899
833 5666243243462814781
834 5720991720963191396
835 5776202505307730807
836 5831878938568572553
837 5888024382927051772
838 5944642220770379683
839 6001735854788672261
840 6059308708072327940
841 6117364224209755180
842 6175905867385450735
843 6234937122478429460
844 6294461495161006496
845 6354482511997932673
846 6415003720545883972
847 6476028689453305888
848 6537561008560613537
849 6599604289000748351
850 6662162163300092206
851 6725238285479739829
852 6788836331157130331
853 6852959997648038714
854 6917613004068928201
855 6982799091439664239
856 7048522022786591026
857 7114785583245971414
858 7181593580167791041
859 7248949843219927546
860 7316858224492685722
861 7385322598603699463
862 7454346862803201362
863 7523934937079660818
864 7594090764265791511
865 7664818310144929105
866 7736121563557780040
867 7808004536509542275
868 7880471264277398845
869 7953525805518385096
870 8027172242377630463
871 8101414680596975657
872 8176257249623966128
873 8251704102721222672
874 8327759417076190051
875 8404427393911264496
876 8481712258594300964
877 8559618260749501021
878 8638149674368682224
879 8717310797922929876
880 8797105954474632029
881 8877539491789898611
882 8958615782451365554
883 9040339223971384801
884 9122714238905601071
885 9205745274966916262
886 9289436805139842373
887 9373793327795243827
888 9458819366805470078
889 9544519471659879386
890 9630898217580754645
891 9717960205639612150
892 9805710062873904190
893 9894152442404116355
894 9983292023551260446
895 10073133511954763878
896 10163681639690756467
897 10254941165390755493
898 10346916874360749932
899 10439613578700684751
900 10533036117424346161
901 10627189356579648724
902 10722078189369325211
903 10817707536272020109
904 10914082345163787676
905 11011207591439995444
906 11109088278137634071
907 11207729436058034444
908 11307136123889992936
909 11407313428333305721
910 11508266464222713052
911 11610000374652254408
912 11712520331100035417
913 11815831533553407463
914 11919939210634560886
915 12024848619726532685
916 12130565047099629635
917 12237093808038267730
918 12344440246968228865
919 12452609737584335671
920 12561607682978545418
921 12671439515768463902
922 12782110698226280233
923 12893626722408123442
924 13005993110283841826
925 13119215413867205951
926 13233299215346536234
927 13348250127215756026
928 13464073792405871119
929 13580775884416876601
930 13698362107450091984
931 13816838196540925531
932 13936209917692068709
933 14056483068007121696
934 14177663475824650871
935 14299757000852679217
936 14422769534303610568
937 14546706999029588632
938 14671575349658291723
939 14797380572729164136
940 14924128686830085100
941 15051825742734476245
942 15180477823538848520
943 15310091044800789500
944 15440671554677392021
945 15572225534064125083
946 15704759196734147962
947 15838278789478068473
948 15972790592244146327
949 16108300918278942526
950 16244816114268415741
951 16382342560479466619
952 16520886670901930966
953 16660454893391022754
954 16801053709810227901
955 16942689636174649774
956 17085369222794807366
957 17229099054420887099
958 17373885750387449206
959 17519735964758589646
960 17666656386473558507
961 17814653739492835853
962 17963734782944665972
963 18113906311272050983
964 18265175154380204761
965 18417548177784468140
966 18571032282758686355
967 18725634406484049685
968 18881361522198398260
969 19038220639345991996
970 19196218803727746623
971 19355363097651936772
972 19515660640085367088
973 19677118586805012337
974 19839744130550127476
975 20003544501174828656
976 20168526965801146129
977 20334698828972550031
978 20502067432807950014
979 20670640157156169701
980 20840424419750896939
981 21011427676366110826
982 21183657420971986489
983 21357121185891278591
984 21531826541956184546
985 21707781098665688422
986 21884992504343386513
987 22063468446295795562
988 22243216650971144618
989 22424244884118651511
990 22606560950948284930
991 22790172696291013090
992 22975088004759539975
993 23161314800909530145
994 23348861049401323096
995 23537734755162138163
996 23727943963548770957
997 23919496760510782328
998 24112401272754180847
999 24306665667905599801
1000 24502298154676969696