3 1
4 71
5 491
6 2522
7 9263
8 27723
9 71480
10 163908
11 345657
12 679802
13 1252185
14 2203724
15 3715206
16 6041979
17 9510283
18 14591324
19 21788606
20 31894205
21 45741815
22 64467383
23 89363919
24 122254946
25 164721244
26 219526449
27 289133792
28 377013829
29 486522424
30 622759365
31 789817312
32 994599793
33 1242696278
34 1542526858
35 1901677518
36 2331785315
37 2840280659
38 3443134366
39 4151428218
40 4981964674
41 5949421549
42 7076474742
43 8377723573
44 9883357150
45 11611358993
46 13594993408
47 15859099532
48 18445721774
49 21376155000
50 24704187092
51 28462855237
52 32706180309
53 37472193387
54 42834206491
55 48825973748
56 55537219213
57 63010471517
58 71339178127
59 80584480495
60 90859057661
61 102206727310
62 114772656056
63 128626220235
64 143903935997
65 160685427703
66 179152788216
67 199368846184
68 221551207154
69 245783304611
70 272275458292
71 301154447585
72 332667887740
73 366892612400
74 404155729403
75 444576439860
76 488460565908
77 535938310006
78 587402824758
79 642954978408
80 703035905784
81 767796312684
82 837654968299
83 912831822731
84 993845714886
85 1080764890846
86 1174266069904
87 1274533474253
88 1382134970774
89 1497312498029
90 1620770603542
91 1752680796019
92 1893860426849
93 2044518705649
94 2205465399641
95 2377020857057
96 2560132394884
97 2754866797733
98 2962430744590
99 3183098619990
100 3417861291637
101 3667079501466
102 3932023887865
103 4212856391103
104 4511077707735
105 4826897418732
106 5161701335292
107 5515964770125
108 5891334089835
109 6287792590008
110 6707353052882
111 7150445794106
112 7618640931391
113 8112449775444
114 8634001406850
115 9183403214819
116 9763149347183
117 10373401004318
118 11016526625624
119 11693127015236
120 12405697111643
121 13154211396609
122 13941855255682
123 14769127161856
124 15638691847636
125 16550970583635
126 17509480750942
127 18514100327673
128 19568725817332
129 20673636829110
130 21832109913439
131 23045258762477
132 24316892483541
133 25646521270903
134 27039367415845
135 28495702667616
136 30019604060546
137 31611636301576
138 33276986036171
139 35015383300586
140 36832601943819
141 38728729687848
142 40708876456385
143 42774185582161
144 44930528298997
145 47176827921543
146 49520732323026
147 51962477647835
148 54508056706011
149 57157941036497
150 59919697147877
151 62792791113550
152 65785319032189
153 68897310600560
154 72136271692725
155 75503059908264
156 79006660410932
157 82644698454776
158 86428572978485
159 90358330887913
160 94441854842514
161 98680171343744
162 103083375403356
163 107650407655810
164 112393607036933
165 117311509285893
166 122415201868980
167 127705640293637
168 133195016646020
169 138879926690939
170 144775518540850
171 150882115930442
172 157210679729630
173 163761592447371
174 170550179024633
175 177573194516553
176 184847680808031
177 192371563712331
178 200159799313905
179 208213735737235
180 216549327526551
181 225161870202701
182 234072168974439
183 243279366567229
184 252799305092473
185 262631052954108
186 272795681155823
187 283288049328004
188 294132142894780
189 305323837513269
190 316882716420089
191 328810658451767
192 341128718454316
193 353829840701906
194 366942661013897
195 380464659839575
196 394417282599421
197 408797846635896
198 423635245532202
199 438922356671517
200 454688416540342
201 470930223378074
202 487672048997062
203 504915605365303
204 522690649959331
205 540983639939015
206 559835239281304
207 579239607418382
208 599225055357909
209 619789184542151
210 640966343811201
211 662747867090605
212 685173468763941
213 708235183006711
214 731968366102732
215 756371284256536
216 781482718672989
217 807285784181847
218 833830530544303
219 861111350274292
220 889162642618767
221 917980919459260
222 947611861283387
223 978041957967326
224 1009322836722921
225 1041441937888318
226 1074444346407279
227 1108327323695383
228 1143142647345113
229 1178865369964326
230 1215560376767151
231 1253219527081126
232 1291884628308333
233 1331550801745896
234 1372278012192210
235 1414044905211362
236 1456920472441222
237 1500884461453774
238 1545996540524441
239 1592252176711524
240 1639711371480510
241 1688347315074231
242 1738237849413604
243 1789372038425545
244 1841808535872971
245 1895531714183731
246 1950620978264498
247 2007046446613546
248 2064894587063135
249 2124142854394606
250 2184857605344473
251 2247038581885660
252 2310760291442593
253 2375981788044344
254 2442809298224293
255 2511220860031021
256 2581289034958107
257 2652996604929075
258 2726441344974073
259 2801584858676505
260 2878530657021635
261 2957251053062383
262 3037831882253274
263 3120265262921563
264 3204649659438186
265 3290927547408321
266 3379231369992634
267 3469530889192244
268 3561919538923889
269 3656373321854550
270 3753006871146362
271 3851778936890175
272 3952811351433151
273 4056069897914046
274 4161661041384817
275 4269568532932547
276 4379918928760696
277 4492634388852854
278 4607883385979244
279 4725626555266932
280 4845968377274206
281 4968884770313899
282 5094513036398059
283 5222797960816507
284 5353902935000300
285 5487765866341593
286 5624527423959916
287 5764162225679294
288 5906817522067381
289 6052410423005398
290 6201125013555672
291 6352929539369774
292 6507944585576824
293 6666134478407682
294 6827682685211401
295 6992497419522047
296 7160781402378036
297 7332462906780193
298 7507706610293204
299 7686485234864745
300 7868976212855885
301 8055067540165087
302 8244993975088327
303 8438701251049029
304 8636346475695381
305 8837877247199920
306 9043506585000338
307 9253134591370205
308 9467003852821386
309 9685019076819104
310 9907375662078235
311 10134047761944636
312 10365233983792406
313 10600808287261422
314 10841055162376284
315 11085889647538076
316 11335515905835079
317 11589851174560491
318 11849170670634732
319 12113344512056978
320 12382643265868590
321 12656980219612332
322 12936565963995627
323 13221364634650791
324 13511638619475874
325 13807202467173755
326 14108412202846546
327 14415165433525602
328 14727689924112323
329 15045912124710423
330 15370115135913032
331 15700167162178288
332 16036396534137643
333 16378672763932002
334 16727279005296195
335 17082142916831188
336 17443577156496120
337 17811358489480249
338 18185909605717001
339 18567112753266219
340 18955227173246324
341 19350159634029366
342 19752263285859863
343 20161358297425397
344 20577842350157691
345 21001545105543727
346 21432803243223383
347 21871529886434254
348 22318104080095409
349 22772260742424009
350 23234470804315175
351 23704610525707453
352 24182968561131548
353 24669440828286205
354 25164448772573999
355 25667760696620127
356 26179864819994152
357 26700536551751161
358 27230180814627590
359 27768699302360431
360 28316494094286870
361 28873290255892442
362 29439623424762722
363 30015338777812924
364 30600814700374902
365 31195861433285938
366 31801018154343765
367 32415983190962362
368 33041327430943019
369 33676811729193653
370 34322858954411768
371 34979388270667820
372 35646859260232290
373 36324918760332867
374 37014253365771963
375 37714625950227052
376 38426470801112627
377 39149597488761216
378 39884594507313572
379 40631142365437242
380 41389865219423164
381 42160501060773729
382 42943550872915774
383 43738888844980088
384 44547091236989598
385 45367702353331391
386 46201503375189986
387 47048226780394244
388 47908413502688955
389 48781805315344262
390 49669082062396636
391 50569879144451499
392 51484902616165313
393 52413843563963743
394 53357300680743067
395 54315086929511956
396 55287896654681525
397 56275175845231241
398 57277863376883481
399 58295646564219585
400 59329048829918193
401 60377878181987321
402 61442852444010825
403 62523552413369906
404 63620865708971037
405 64734327294150044
406 65864690104780510
407 67011695332570554
408 68176140872792351
409 69357431399655980
410 70556554297667557
411 71773216510369802
412 73008039572014443
413 74260704674377027
414 75532138160599332
415 76821775705885387
416 78130623490715463
417 79458205487724136
418 80805326566738686
419 82171746684791355
420 83558326240463134
421 84964366472485890
422 86391049096129643
423 87837975943731613
424 89305898947415205
425 90794416375957475
426 92304597826933030
427 93835777156512118
428 95389144903883509
429 96964114350644066
430 98561589867271350
431 100181336578657769
432 101824261172793553
433 103489634753900873
434 105178786136978256
435 106891194171127495
436 108627775523065368
437 110388031440216891
438 112173219137429188
439 113982581083806915
440 115817372350702825
441 117677014481423962
442 119562465114290050
443 121473442823632507
444 123411128454964426
445 125374483752300356
446 127365152213492872
447 129382491758693110
448 131427519765353267
449 133499724922288068
450 135600380401872346
451 137728754376669325
452 139886247062741706
453 142072147727080091
454 144287681690597448
455 146532365972891440
456 148807548548759342
457 151112089822767791
458 153447804438527632
459 155814040735200727
460 158211860091652386
461 160640714602395614
462 163102085970424138
463 165595019239231497
464 168121226458697435
465 170679812812360208
466 173272121119022990
467 175897675245621904
468 178558007220835537
469 181251817973173033
470 183981068738368344
471 186745076878477442
472 189545003744867690
473 192380247298641377
474 195252521728694147
475 198160651467911759
476 201106654677904364
477 204089365918375642
478 207110470314894060
479 210169378550886292
480 213267649311083751
481 216404004344097618
482 219580562652229289
483 222796543725561666
484 226053363745774166
485 229350125645815259
486 232688903531171802
487 236068362375200091
488 239490650480009539
489 242954689738507609
490 246462055472819329
491 250012234306059263
492 253607056285861330
493 257244865686973462
494 260928316748663813
495 264656289383692967
496 268430424704640497
497 272249742934990168
498 276116516719697548
499 280029270325735475
500 283990406585501720
501 287998685763304439
502 292055937637738596
503 296161523934149805
504 300317503676667135
505 304521981033390667
506 308777858917931510
507 313083943753289179
508 317442125367947821
509 321851322827036152
510 326313924721762050
511 330828433130566683
512 335397314489640085
513 340019273579831304
514 344696461841223098
515 349427951625290277
516 354216249175149556
517 359059038103701053
518 363959759379480144
519 368916983994605445
520 373932610415826721
521 379005671078086899
522 384138693111644696
523 389329954457853291
524 394582558643879902
525 399894636868196227
526 405268713551235228
527 410703773339560627
528 416202528425524942
529 421762603354630786
530 427387414789116968
531 433075724446160128
532 438829577916930100
533 444647650647220284
534 450533165614489802
535 456483837812460877
536 462503159300037330
537 468589166561377196
538 474744622762823560
539 480968414454080308
540 487263384552745011
541 493626974945565574
542 500063096964014809
543 506570167217189000
544 513150652327759567
545 519802959780959563
546 526530559368305453
547 533330996788709381
548 540208198571748956
549 547159936668887553
550 554189161964992159
551 561294798576618083
552 568479865372822429
553 575741551794801363
554 583084240529213464
555 590506018697746017
556 598009756307543860
557 605593546270336617
558 613261403795424755
559 621010636598956682
560 628845173313287323
561 636762926478524974
562 644766892128763896
563 652855939358378611
564 661033779733436476
565 669296709761226753
566 677650040269108056
567 686091339030085601
568 694623775365848913
569 703245491363393683
570 711960481570325216
571 720766037931579806
572 729666636079971806
573 738659632180429756
574 747748823138892511
575 756932392775530524
576 766214467519281305
577 775591281747398355
578 785068322256521661
579 794643301711246044
580 804319436051834684
581 814094685380042551
582 823973574448756643
583 833952897326958216
584 844037797533997790
585 854225147258339588
586 864519121000661606
587 874917809761662727
588 885425937190081110
589 896039041244759816
590 906763160635295906
591 917595985979848489
592 928540700315345137
593 939595351304849064
594 950764903846458001
595 962045574867310822
596 973443206489239900
597 984954166055414556
598 996583268276559777
599 1008328540290353606
600 1020194504460734640
601 1032176874248793388
602 1044282010046001926
603 1056507080267663160
604 1068856441584756066
605 1081326919972348312
606 1093924636414246733
607 1106645140754115471
608 1119494886034175978
609 1132470215857554944
610 1145575571339771193
611 1158809300878824636
612 1172176442512829887
613 1185672002045409718
614 1199303434307037508
615 1213067234629466259
616 1226967971792402071
617 1241002473397640550
618 1255177241124080353
619 1269487673267142646
620 1283940487189887523
621 1298531755253007691
622 1313266708869815767
623 1328142982604785701
624 1343166479146947669
625 1358331338857924982
626 1373645866592491035
627 1389106202112541029
628 1404717555532064556
629 1420476429974306543
630 1436389563653668379
631 1452452182815875689
632 1468671318677255049
633 1485042927972277423
634 1501572720451791933
635 1518257987905533688
636 1535105437043515899
637 1552108249223746314
638 1569275775812298529
639 1586603820368302970
640 1604097438758328482
641 1621753598432461351
642 1639579087998485918
643 1657568826460773364
644 1675731213506109877
645 1694060532643591488
646 1712563936639422593
647 1731237978053588892
648 1750089991431759718
649 1769113095945597808
650 1788316457328215486
651 1807696294295988314
652 1827257999076861919
653 1846997599323386273
654 1866923824811884918
655 1887029925474661158
656 1907325150728790529
657 1927803846091728510
658 1948473202257122747
659 1969329889023365894
660 1990381475907713046
661 2011620533951021592
662 2033057464914270688
663 2054687669819296069
664 2076517432258910023
665 2098542147538847072
666 2120770725927384026
667 2143196392495713940
668 2165829468759052306
669 2188663541415719599
670 2211706100726289364
671 2234954123933591166
672 2258415216847985308
673 2282081406843669139
674 2305964430441708997
675 2330058448581553231
676 2354371049964069587
677 2378896604950414510
678 2403645684199775292
679 2428610513331423047
680 2453801306603341007
681 2479212222228983659
682 2504850899340811320
683 2530713806877704104
684 2556810327792882433
685 2583130641985631905
686 2609687872613884769
687 2636475665954097394
688 2663501859491257800
689 2690761285820521285
690 2718263977571159025
691 2746002472972051827
692 2773988029160429643
693 2802213375149926894
694 2830687995844148450
695 2859406871938055421
696 2888380478317431850
697 2917598342282591692
698 2947074637841884190
699 2976802784788742418
700 3006790736860790997
701 3037032860756570492
702 3067540290245611284
703 3098304756753955804
704 3129338675727062365
705 3160633884810980725
706 3192200491894621396
707 3224033409623107362
708 3256143960336957705
709 3288520776225636302
710 3321178679563421777
711 3354111164641003062
712 3387326317268263877
713 3420818290730557923
714 3454599591229649635
715 3488659905355991657
716 3523014020932352930
717 3557652161606425237
718 3592585947698760031
719 3627809975419204146
720 3663335211614478378
721 3699150634420819549
722 3735271227023315293
723 3771690229382685246
724 3808417519999910153
725 3845445115416452353
726 3882787721288861379
727 3920433707850642109
728 3958398643604864692
729 3996672872419713761
730 4035267370917930149
731 4074177428544449369
732 4113415101301439097
733 4152967323571869275
734 4192852515652717690
735 4233061221599262917
736 4273604145032486514
737 4314473471306129913
738 4355684158032211464
739 4397225028628085485
740 4439111539520675359
741 4481333887268113204
742 4523904306641790350
743 4566816556985075183
744 4610084590763834890
745 4653693907480861314
746 4697663706061095806
747 4741984406550170677
748 4786668304023725450
749 4831706168738115551
750 4877113761544581735
751 4922879374687646662
752 4969019379106851947
753 5015523641850957680
754 5062405316793065091
755 5109657118767247303
756 5157294854216347386
757 5205301551054464019
758 5253699424248127530
759 5302477875086374303
760 5351648241539970216
761 5401202853363591099
762 5451157724192821740
763 5501499704916700598
764 5552248391409672478
765 5603390008090550272
766 5654940602180253981
767 5706891927063875088
768 5759260335517542444
769 5812029464795372759
770 5865220147691119800
771 5918822946448666356
772 5972850050213936166
773 6027292071571867241
774 6082167941530216072
775 6137462336010147882
776 6193195855715408966
777 6249354655376192485
778 6305955136167439732
779 6362989102811440288
780 6420473813096114821
781 6478391206755139960
782 6536764861244136107
783 6595583310641581698
784 6654861078863103640
785 6714586210092974775
786 6774779791199737852
787 6835425019284544686
788 6896545189235035652
789 6958125133834108812
790 7020181417757927878
791 7082706542417281094
792 7145716893274215702
793 7209194597860916057
794 7273165193078651208
795 7337615456765483518
796 7402561398595801773
797 7467990272702813420
798 7533925072417964381
799 7600347566601193838
800 7667280717991458880
801 7734710510382182062
802 7802653702176216312
803 7871101639926389615
804 7940075322930981057
805 8009551196261479700
806 8079559051333943932
807 8150083694338378909
808 8221142490516921326
809 8292722872277396760
810 8364846557842782950
811 8437496835552068989
812 8510697663318845391
813 8584432493655050808
814 8658721984543364299
815 8733554608765514185
816 8808952506784024868
817 8884892419737517141
818 8961404512000941435
819 9038473982482986798
820 9116117623113298092
821 9194322503980614499
822 9273113248976752793
823 9352469989770807966
824 9432420358893034226
825 9512945264927179785
826 9594066436436374883
827 9675771652866209097
828 9758085777326178898
829 9840983087144958558
830 9924495390247436045
831 10008607866296813507
832 10093337250097270833
833 10178670824549921798
834 10264634432062908562
835 10351205785111554307
836 10438416024839254305
837 10526243009457689753
838 10614711988991804086
839 10703809960880449758
840 10793560310479263277
841 10883938168251448624
842 10974976275778355095
843 11066658676951327747
844 11159006338595314917
845 11252001056454150290
846 11345673749514630558
847 11439999455616499486
848 11535009730816876960
849 11630684553355831871
850 11727046183081318214
851 11824084143520800094
852 11921823380102268423
853 12020235303188148162
854 12119358310736994674
855 12219171430378318169
856 12319697714540841255
857 12420919068509094445
858 12522867340012464297
859 12625517099176381626
860 12728901601792154852
861 12832998825094899545
862 12937833289206581619
863 13043392421393305885
864 13149704380664956843
865 13256737866299463106
866 13364532777534006934
867 13473068183781090757
868 13582369071192889890
869 13692415587673500880
870 13803240409976158000
871 13914817824840225888
872 14027181975395640324
873 14140309983431989903
874 14254229745575156884
875 14368924562128756166
876 14484426791108579909
877 14600700908723925053
878 14717792210780276767
879 14835678145119249435
880 14954381335409966887
881 15073885061970120872
882 15194221207676899280
883 15315362758318396260
884 15437348924531812864
885 15560151434140065611
886 15683802113147939188
887 15808282846270281555
888 15933627981332012307
889 16059801297245980890
890 16186845962205464693
891 16314741491487794901
892 16443513040189046491
893 16573139351366961371
894 16703659737676312164
895 16835040796909287556
896 16967324912882974646
897 17100482478307831914
898 17234546544016238566
899 17369500229483727230
900 17505376212510043358
901 17642138748181693960
902 17779834430607616427
903 17918439167042284435
904 18057980922917435197
905 18198436288110251389
906 18339846520537821796
907 18482176819608292699
908 18625473740622726040
909 18769704740267749170
910 18914904034888299123
911 19061053949702663753
912 19208189019005527276
913 19356270778709993767
914 19505350913492006985
915 19655401234872430813
916 19806454138605621973
917 19958481644764894696
918 20111529898165014011
919 20265562287957746001
920 20420623086204990380
921 20576684431959321734
922 20733777799224119579
923 20891886071755635613
924 21051050172633885473
925 21211221626052674712
926 21372459640890588369
927 21534733440522600109
928 21698075780965799796
929 21862461965652674171
930 22027933995222432866
931 22194456942172013829
932 22362078783364855243
933 22530765265123785924
934 22700557370490911705
935 22871430475343726097
936 23043427681181534084
937 23216502025199881052
938 23390712846117161696
939 23566028688124034844
940 23742484030442425512
941 23920051535337760584
942 24098778414941265153
943 24278625478020313028
944 24459645649733483041
945 24641800339840053482
946 24825131493449394611
947 25009614608626210885
948 25195297926591857506
949 25382129501379875533
950 25570171137899927282
951 25759393062566022911
952 25949826829832990296
953 26141445556304324193
954 26334300839222393188
955 26528347532619906753
956 26723645131629739710
957 26920150327542844726
958 27117910745824215322
959 27316900270784691502
960 27517163626583582026
961 27718651504025059724
962 27921426975658044597
963 28125457807202860159
964 28330783438264095992
965 28537368023953868247
966 28745270676934789349
967 28954440817076617900
968 29164941252315613074
969 29376730592000127863
970 29589851066620249050
971 29804281700062040216
972 30020068745225563028
973 30237158012209704783
974 30455620133126027606
975 30675415761720518037
976 30896587676474195386
977 31119100616036893829
978 31343014397185319225
979 31568279190312214006
980 31794957559330020404
981 32023004996624123390
982 32252470963612342478
983 32483327559712176301
984 32715629710916134290
985 32949314222319750354
986 33184458836921396957
987 33421021305876403607
988 33659047687772360856
989 33898500432938029345
990 34139440087739177572
991 34381817400291838298
992 34625695079006271103
993 34871029816442253277
994 35117872496384318141
995 35366191102000828634
996 35616046802337012268
997 35867370161310404519
998 36120246351719881315
999 36374630779091485754
1000 36630567032260038270