4 1
5 2
6 5
7 13
8 34
9 88
10 221
11 530
12 1204
13 2587
14 5270
15 10220
16 18955
17 33775
18 58060
19 96647
20 156299
21 246280
22 379051
23 571103
24 843944
25 1225258
26 1750255
27 2463232
28 3419366
29 4686761
30 6348772
31 8506630
32 11282393
33 14822249
34 19300198
35 24922141
36 31930405
37 40608734
38 51287777
39 64351105
40 80241790
41 99469580
42 122618705
43 150356350
44 183441832
45 222736519
46 269214530
47 323974256
48 388250743
49 463428979
50 551058128
51 652866755
52 770779087
53 906932356
54 1063695271
55 1243687667
56 1449801380
57 1685222398
58 1953454339
59 2258343308
60 2604104186
61 2995348405
62 3437113264
63 3934892842
64 4494670565
65 5122953485
66 5826808330
67 6613899385
68 7492528265
69 8471675642
70 9561044989
71 10771108405
72 12113154586
73 13599339008
74 15242736389
75 17057395498
76 19058396380
77 21261910067
78 23685260846
79 26346991156
80 29266929187
81 32466259255
82 35967595028
83 39795055679
84 43974345043
85 48532833856
86 53499645155
87 58905742919
88 64784024032
89 71169413650
90 78098964055
91 85611957080
92 93750010190
93 102557186305
94 112080107452
95 122368072334
96 133473177905
97 145450445041
98 158357948398
99 172256950549
100 187212040493
101 203291276630
102 220566334297
103 239112657961
104 259009618166
105 280340673332
106 303193536505
107 327660347158
108 353837848144
109 381827567903
110 411736008026
111 443674836280
112 477761085199
113 514117356347
114 552872030360
115 594159482875
116 638120306455
117 684901538620
118 734656896095
119 787547015387
120 843739699804
121 903410173030
122 966741339371
123 1033924050788
124 1105157380834
125 1180648905613
126 1260614991880
127 1345281092402
128 1434882048701
129 1529662401301
130 1629876707602
131 1735789867505
132 1847677456913
133 1965826069234
134 2090533665013
135 2222109929821
136 2360876640530
137 2507168040104
138 2661331221037
139 2823726517570
140 2994727906820
141 3174723418955
142 3364115556550
143 3563321723260
144 3772774661947
145 3992922902399
146 4224231218780
147 4467181096951
148 4722271211803
149 4990017914744
150 5270955731483
151 5565637870255
152 5874636740632
153 6198544483066
154 6537973509311
155 6893557053872
156 7265949736630
157 7655828136793
158 8063891378324
159 8490861726998
160 8937485199241
161 9404532182905
162 9892798070134
163 10403103902477
164 10936297028405
165 11493251773390
166 12074870122705
167 12682082417105
168 13315848061550
169 13977156247132
170 14667026686369
171 15386510362030
172 16136690289656
173 16918682293943
174 17733635799154
175 18582734633728
176 19467197849255
177 20388280553987
178 21347274761056
179 22345510251571
180 23384355452767
181 24465218331380
182 25589547302423
183 26758832153539
184 27974604985108
185 29238441166286
186 30551960307155
187 31916827247164
188 33334753060042
189 34807496075365
190 36336862916960
191 37924709558330
192 39572942395285
193 41283519335965
194 43058450908442
195 44899801386089
196 46809689930905
197 48790291754986
198 50843839300333
199 52972623437189
200 55178994681098
201 57465364428880
202 59834206213717
203 62288056979546
204 64829518374956
205 67461258066787
206 70186011073630
207 73006581119428
208 75925842007379
209 78946739014343
210 82072290305956
211 85305588372655
212 88649801486819
213 92108175181232
214 95684033749075
215 99380781765655
216 103201905632080
217 107150975141090
218 111231645065255
219 115447656767752
220 119802839835934
221 124301113737905
222 128946489502316
223 133743071421598
224 138695058778849
225 143806747598593
226 149082532421630
227 154526908104197
228 160144471641661
229 165939924016966
230 171918072074057
231 178083830416505
232 184442223331558
233 190998386739844
234 197757570170953
235 204725138765126
236 211906575301280
237 219307482251599
238 226933583862922
239 234790728265160
240 242884889606975
241 251222170218955
242 259808802804520
243 268651152658795
244 277755719915687
245 287129141823404
246 296778195048655
247 306709798009771
248 316931013238988
249 327449049774134
250 338271265579963
251 349405169999380
252 360858426234802
253 372638853859901
254 384754431361976
255 397213298715202
256 410023759985005
257 423194285963813
258 436733516838434
259 450650264889313
260 464953517221921
261 479652438530530
262 494756373894629
263 510274851608237
264 526217586042370
265 542594480540920
266 559415630350205
267 576691325582450
268 594432054213460
269 612648505114747
270 631351571120374
271 650552352128780
272 670262158239851
273 690492512927503
274 711255156248044
275 732562048084583
276 754425371427755
277 776857535693032
278 799871180074891
279 823479176938111
280 847694635246472
281 872530904029130
282 898001575884943
283 924120490525024
284 950901738353798
285 978359664088841
286 1006508870419780
287 1035364221706534
288 1064940847717177
289 1095254147405705
290 1126319792729990
291 1158153732510205
292 1190772196328005
293 1224191698466750
294 1258429041893057
295 1293501322279969
296 1329425932072030
297 1366220564592556
298 1403903218193393
299 1442492200447454
300 1482006132384328
301 1522463952769255
302 1563884922425762
303 1606288628602256
304 1649694989382871
305 1694124258142867
306 1739597028048880
307 1786134236604323
308 1833757170240239
309 1882487468951908
310 1932347130981511
311 1983358517547155
312 2035544357618564
313 2088927752739742
314 2143532181898915
315 2199381506446060
316 2256499975058330
317 2314912228753685
318 2374643305953040
319 2435718647591242
320 2498164102277189
321 2562005931503405
322 2627270814905386
323 2693985855571033
324 2762178585400489
325 2831876970516698
326 2903109416727005
327 2975904775036117
328 3050292347210746
329 3126301891396256
330 3203963627785637
331 3283308244341130
332 3364366902568828
333 3447171243346579
334 3531753392805518
335 3618145968265556
336 3706382084225155
337 3796495358405719
338 3888519917850932
339 3982490405081375
340 4078441984304755
341 4176410347682080
342 4276431721650115
343 4378542873300455
344 4482781116815552
345 4589184319962034
346 4697790910641655
347 4808639883500216
348 4921770806594798
349 5037223828119649
350 5155039683191068
351 5275259700691630
352 5397925810174097
353 5523080548825361
354 5650767068490766
355 5781029142759157
356 5913911174109005
357 6049458201115958
358 6187715905722169
359 6328730620567753
360 6472549336384726
361 6619219709453780
362 6768790069124249
363 6921309425397622
364 7076827476574960
365 7235394616968575
366 7397061944678330
367 7561881269432920
368 7729905120496495
369 7901186754640987
370 8075780164184504
371 8253740085096155
372 8435122005167671
373 8619982172252188
374 8808377602570559
375 9000366089085563
376 9196006209944380
377 9395357336989702
378 9598479644339851
379 9805434117038276
380 10016282559772802
381 10231087605665005
382 10449912725130088
383 10672822234807634
384 10899881306563613
385 11131155976564021
386 11366713154420530
387 11606620632408529
388 11850947094757937
389 12099762127017170
390 12353136225490645
391 12611140806750205
392 12873848217220850
393 13141331742841160
394 13413665618798797
395 13690925039341474
396 13973186167663780
397 14260526145870251
398 14553023105015078
399 14850756175218844
400 15153805495862683
401 15462252225860255
402 15776178554007932
403 16095667709413591
404 16420803972004411
405 16751672683114072
406 17088360256149755
407 17430954187339343
408 17779543066559224
409 18134216588243098
410 18495065562372191
411 18862181925547280
412 19235658752142934
413 19615590265544377
414 20002071849467380
415 20395200059361590
416 20795072633897705
417 21201788506538905
418 21615447817196950
419 22036151923973357
420 22464003414986069
421 22899106120282030
422 23341565123836081
423 23791486775636593
424 24248978703858254
425 24714149827122428
426 25187110366845505
427 25667971859675662
428 26156847170018456
429 26653850502651671
430 27159097415429842
431 27672704832078880
432 28194791055081223
433 28725475778651939
434 29264880101806208
435 29813126541518611
436 30370339045974655
437 30936643007914964
438 31512165278072567
439 32097034178703715
440 32691379517212660
441 33295332599870830
442 33909026245630835
443 34532594800035740
444 35166174149224042
445 35809901734030789
446 36463916564185280
447 37128359232605786
448 37803371929791733
449 38489098458313789
450 39185684247402298
451 39893276367634505
452 40612023545721017
453 41342076179391946
454 42083586352383181
455 42836707849523237
456 43601596171921130
457 44378408552255728
458 45167303970167029
459 45968443167749818
460 46781988665150156
461 47608104776265155
462 48446957624546494
463 49298715158908132
464 50163547169738675
465 51041625305018855
466 51933123086544580
467 52838215926256015
468 53757081142673155
469 54689897977438352
470 55636847611966259
471 56598113184201655
472 57573879805485616
473 58564334577530498
474 59569666609504199
475 60590067035224168
476 61625729030461630
477 62676847830356497
478 63743620746943436
479 64826247186789566
480 65924928668744257
481 67039868841801505
482 68171273503075358
483 69319350615888869
484 70484310327977053
485 71666364989804326
486 72865729172996905
487 74082619688890649
488 75317255607194822
489 76569858274772260
490 77840651334536425
491 79129860744465830
492 80437714796736320
493 81764444136971695
494 83110281783613162
495 84475463147408104
496 85860226051018655
497 87264810748750571
498 88689459946402888
499 90134418821238859
500 91599935042078663
501 93086258789514380
502 94593642776247727
503 96122342267551051
504 97672615101852076
505 99244721711442902
506 100838925143313755
507 102455491080111988
508 104094687861226834
509 105756786504000413
510 107442060725065496
511 109150786961810530
512 110883244393972429
513 112639714965357637
514 114420483405691970
515 116225837252599745
516 118056066873712705
517 119911465488909250
518 121792329192684485
519 123698956976651597
520 125631650752175074
521 127590715373136280
522 129576458658831901
523 131589191417005778
524 133629227467014644
525 135696883663128283
526 137792479917964630
527 139916339226060332
528 142068787687577291
529 144250154532145711
530 146460772142844172
531 148700976080317255
532 150971105107031243
533 153271501211668424
534 155602509633660523
535 157964478887861791
536 160357760789362280
537 162782710478441834
538 165239686445665327
539 167729050557119680
540 170251168079793190
541 172806407707097705
542 175395141584534180
543 178017745335502150
544 180674598087253657
545 183366082496992169
546 186092584778117030
547 188854494726613981
548 191652205747592293
549 194486114881969054
550 197356622833301153
551 200264133994765505
552 203209056476288062
553 206191802131822156
554 209212786586776721
555 212272429265594942
556 215371153419483880
557 218509386154295623
558 221687558458560514
559 224906105231673008
560 228165465312230711
561 231466081506527155
562 234808400617198864
563 238192873472027267
564 241619954952896015
565 245090104024904260
566 248603783765636455
567 252161461394589235
568 255763608302755940
569 259410700082369342
570 263103216556803139
571 266841641810632780
572 270626464219856186
573 274458176482274933
574 278337275648036464
575 282264263150337898
576 286239644836292005
577 290263930997955917
578 294337636403523146
579 298461280328679481
580 302635386588123337
581 306860483567251130
582 311137104254008253
583 315465786270906229
584 319847071907206618
585 324281508151272256
586 328769646723086405
587 333312044106940394
588 337909261584290332
589 342561865266783475
590 347270426129454830
591 352035520044094580
592 356857727812786915
593 361737635201620855
594 366675832974573652
595 371672916927567359
596 376729487922699155
597 381846151922646016
598 387023520025244323
599 392262208498244999
600 397562838814244768
601 402926037685794130
602 408352437100682647
603 413842674357402136
604 419397392100788366
605 425017238357841857
606 430702866573728380
607 436454935647959758
608 442274109970755569
609 448161059459586353
610 454116459595898926
611 460140991462024405
612 466235341778269549
613 472400202940192022
614 478636273056060185
615 484944255984498025
616 491324861372315830
617 497778804692527220
618 504306807282553145
619 510909596382613462
620 517587905174306704
621 524342472819378655
622 531174044498680346
623 538083371451316088
624 545071211013982159
625 552138326660496763
626 559285488041521880
627 566513471024477627
628 573823057733649751
629 581215036590490876
630 588690202354116127
631 596249356161993755
632 603893305570831388
633 611622864597658534
634 619438853761105963
635 627342100122882596
636 635333437329450530
637 643413705653898829
638 651583752038016712
639 659844430134566770
640 668196600349758845
641 676641129885925205
642 685178892784397650
643 693810769968587185
644 702537649287266897
645 711360425558058674
646 720280000611124405
647 729297283333062301
648 738413189711008978
649 747628642876947944
650 756944573152225133
651 766361918092272130
652 775881622531537732
653 785504638628628491
654 795231925911658886
655 805064451323811772
656 815003189269109755
657 825049121658398143
658 835203237955540124
659 845466535223824823
660 855840018172588891
661 866324699204052280
662 876921598460368859
663 887631743870892527
664 898456171199659480
665 909395924093087290
666 920452054127891455
667 931625620859220080
668 942917691869007350
669 954329342814546457
670 965861657477282644
671 977515727811827030
672 989292653995191881
673 1001193544476247993
674 1013219516025404854
675 1025371693784514253
676 1037651211316998005
677 1050059210658200462
678 1062596842365966481
679 1075265265571445521
680 1088065648030122542
681 1100999166173076380
682 1114067005158466273
683 1127270358923247214
684 1140610430235114808
685 1154088430744680311
686 1167705581037876530
687 1181463110688595264
688 1195362258311556967
689 1209404271615413315
690 1223590407456083360
691 1237921931890323955
692 1252400120229535135
693 1267026257093801140
694 1281801636466167767
695 1296727561747156739
696 1311805345809517780
697 1327036311053219086
698 1342421789460676883
699 1357963122652224764
700 1373661661941823498
701 1389518768393012005
702 1405535812875100192
703 1421714176119604346
704 1438055248776925781
705 1454560431473273437
706 1471231134867831130
707 1488068779710170153
708 1505074796897907929
709 1522250627534613418
710 1539597722987959981
711 1557117544948126405
712 1574811565486446794
713 1592681267114310032
714 1610728142842309525
715 1628953696239643930
716 1647359441493769580
717 1665946903470305315
718 1684717617773190430
719 1703673130805096452
720 1722814999828093459
721 1742144793024571655
722 1761664089558418916
723 1781374479636455023
724 1801277564570123299
725 1821374956837440368
726 1841668280145204755
727 1862159169491465047
728 1882849271228248336
729 1903740243124549666
730 1924833754429583207
731 1946131485936295880
732 1967635130045144158
733 1989346390828134769
734 2011266984093130028
735 2033398637448418526
736 2055743090367551905
737 2078302094254448449
738 2101077412508764222
739 2124070820591532485
740 2147284106091072125
741 2170719068789165830
742 2194377520727508745
743 2218261286274428345
744 2242372202191876262
745 2266712117702692804
746 2291282894558144905
747 2316086407105738246
748 2341124542357304288
749 2366399200057362959
750 2391912292751761738
751 2417665745856591880
752 2443661497727382527
753 2469901499728573451
754 2496387716303267176
755 2523122125043261227
756 2550106716759361255
757 2577343495551975788
758 2604834478881993359
759 2632581697641942763
760 2660587196227437196
761 2688853032608903030
762 2717381278403593979
763 2746174018947891412
764 2775233353369891570
765 2804561394662280445
766 2834160269755497080
767 2864032119591186050
768 2894179099195939885
769 2924603377755332197
770 2955307138688242274
771 2986292579721471905
772 3017561912964655201
773 3049117364985462178
774 3080961176885096869
775 3113095604374090733
776 3145522917848392130
777 3178245402465752632
778 3211265358222410941
779 3244585100030075186
780 3278206957793204372
781 3312133276486589755
782 3346366416233236918
783 3380908752382549324
784 3415762675588814123
785 3450930591889990991
786 3486414922786804780
787 3522218105322142759
788 3558342592160757227
789 3594790851669274280
790 3631565367996509515
791 3668668641154091455
792 3706103187097393480
793 3743871537806775050
794 3781976241369133007
795 3820419862059763744
796 3859204980424537030
797 3898334193362382281
798 3937810114208088068
799 3977635372815415654
800 4017812615640527353
801 4058344505825730505
802 4099233723283537862
803 4140482964781045181
804 4182094944024626821
805 4224072391744950142
806 4266418055782309505
807 4309134701172280673
808 4352225110231696414
809 4395692082644944108
810 4439538435550586161
811 4483767003628304030
812 4528380639186166664
813 4573382212248224167
814 4618774610642427490
815 4664560740088874960
816 4710743524288386455
817 4757325905011406035
818 4804310842187233840
819 4851701313993588067
820 4899500316946497839
821 4947710865990527780
822 4996335994589335111
823 5045378754816560083
824 5094842217447050564
825 5144729472048421598
826 5195043627072950755
827 5245787809949810092
828 5296965167177635546
829 5348578864417434581
830 5400632086585832912
831 5453128037948661130
832 5506069942214882053
833 5559461042630859629
834 5613304602074970218
835 5667603903152557081
836 5722362248291228905
837 5777582959836503194
838 5833269380147795357
839 5889424871694754325
840 5946052817153945530
841 6003156619505882080
842 6060739702132404965
843 6118805508914413130
844 6177357504329944252
845 6236399173552607059
846 6295934022550366030
847 6355965578184679316
848 6416497388309990723
849 6477533021873576599
850 6539076069015748468
851 6601130141170412255
852 6663698871165984947
853 6726785913326669536
854 6790394943574089091
855 6854529659529280807
856 6919193780615050880
857 6984391048158691058
858 7050125225495057719
859 7116400098070014328
860 7183219473544238126
861 7250587181897391905
862 7318507075532661724
863 7386983029381661422
864 7456018941009704785
865 7525618730721446225
866 7595786341666890830
867 7666525739947774645
868 7737840914724316045
869 7809735878322339062
870 7882214666340769529
871 7955281337759504905
872 8028939975047658646
873 8103194684272179988
874 8178049595206850009
875 8253508861441654838
876 8329576660492536880
877 8406257193911524927
878 8483554687397244026
879 8561473390905805976
880 8640017578762081327
881 8719191549771353755
882 8798999627331357688
883 8879446159544700059
884 8960535519331667063
885 9042272104543416796
886 9124660338075558655
887 9207704667982120379
888 9291409567589903612
889 9375779535613228870
890 9460819096269070795
891 9546532799392584580
892 9632925220553024450
893 9720000961170055085
894 9807764648630456872
895 9896220936405225874
896 9985374504167069405
897 10075230057908298101
898 10165792330059115378
899 10257066079606305169
900 10349056092212318833
901 10441767180334762130
902 10535204183346283157
903 10629371967654862141
904 10724275426824503986
905 10819919481696334472
906 10916309080510101005
907 11013449199026078818
908 11111344840647383524
909 11210001036542690923
910 11309422845769364966
911 11409615355396994780
912 11510583680631341659
913 11612332964938696927
914 11714868380170651580
915 11818195126689278615
916 11922318433492728955
917 12027243558341241880
918 12132975787883570875
919 12239520437783825807
920 12346882852848732344
921 12455068407155309530
922 12564082504178966431
923 12673930576922018768
924 12784618088042626454
925 12896150529984152953
926 13008533425104947380
927 13121772325808550262
928 13235872814674323881
929 13350840504588508121
930 13466681038875702742
931 13583400091430777005
932 13701003366851207573
933 13819496600569845614
934 13938885558988114033
935 14059176039609635761
936 14180373871174294030
937 14302484913792725564
938 14425515059081247617
939 14549470230297219790
940 14674356382474841560
941 14800179502561386455
942 14926945609553873810
943 15054660754636179040
944 15183331021316583367
945 15312962525565763939
946 15443561415955225280
947 15575133873796173011
948 15707686113278830783
949 15841224381612201364
950 15975754959164272823
951 16111284159602670755
952 16247818330035757492
953 16385363851154179246
954 16523927137372862131
955 16663514636973458012
956 16804132832247241130
957 16945788239638456453
958 17088487409888120704
959 17232236928178277018
960 17377043414276704181
961 17522913522682081405
962 17669853942769609594
963 17817871398937090057
964 17966972650751461625
965 18117164493095797130
966 18268453756316760205
967 18420847306372523365
968 18574352044981148330
969 18728974909769429552
970 18884722874422201909
971 19041602948832113530
972 19199622179249864716
973 19358787648434913923
974 19519106475806651774
975 19680585817596044068
976 19843232866997744755
977 20007054854322679847
978 20172059047151103236
979 20338252750486125391
980 20505643306907715907
981 20674238096727180880
982 20844044538142116083
983 21015070087391836919
984 21187322238913286128
985 21360808525497420226
986 21535536518446075655
987 21711513827729315624
988 21888748102143258622
989 22067247029468389585
990 22247018336628354700
991 22428069789849240830
992 22610409194819340545
993 22794044396849403745
994 22978983281033376862
995 23165233772409630629
996 23352803836122677405
997 23541701477585379046
998 23731934742641646313
999 23923511717729630809
1000 24116440530045410438