3 1
4 25
5 186
6 881
7 3146
8 9264
9 23810
10 55058
11 117205
12 233135
13 438544
14 786541
15 1354696
16 2252202
17 3630684
18 5694984
19 8718963
20 13060515
21 19184110
22 27681103
23 39300096
24 54974216
25 75861038
26 103377456
27 139251749
28 185567453
29 244828780
30 320015885
31 414665890
32 532940080
33 679724056
34 860708610
35 1082510241
36 1352768931
37 1680291786
38 2075168049
39 2548940440
40 3114739498
41 3787483770
42 4584037640
43 5523443639
44 6627103791
45 7919049776
46 9426150227
47 11178419704
48 13209257144
49 15555797428
50 18259180600
51 21364953025
52 24923370153
53 28989847926
54 33625305441
55 38896670898
56 44877263256
57 51647361094
58 59294626378
59 67914736485
60 77611857695
61 88499345180
62 100700264685
63 114348170336
64 129587677970
65 146575320496
66 165480181856
67 186484835251
68 209786035459
69 235595751370
70 264141920463
71 295669574760
72 330441667920
73 368740300434
74 410867616216
75 457147140181
76 507924748477
77 563570116824
78 624477776429
79 691068679418
80 763791336360
81 843123513740
82 929573457578
83 1023681720481
84 1126022485091
85 1237205527558
86 1357877635681
87 1488724725664
88 1630473359778
89 1783893012990
90 1949797705680
91 2129048427495
92 2322554878815
93 2531278070716
94 2756232180355
95 2998487322576
96 3259171536656
97 3539473737416
98 3840645825744
99 4164005840225
100 4510940196953
101 4882907036050
102 5281438610225
103 5708144834554
104 6164715814816
105 6652925623786
106 7174634975202
107 7731795219669
108 8326451185839
109 8960745404808
110 9636921108045
111 10357326705880
112 11124418948378
113 11940767649636
114 12809059035416
115 13732100722643
116 14712825241731
117 15754295299334
118 16859707481903
119 18032397791920
120 19275845558840
121 20593679258710
122 21989680618720
123 23467790750821
124 25032114456765
125 26686926664356
126 28436676961581
127 30285996345906
128 32239701971904
129 34302804246880
130 36480511799218
131 38778238907265
132 41201610719555
133 43756471027874
134 46448887721841
135 49285160942216
136 52271828777402
137 55415675782114
138 58723738949624
139 62203316607223
140 65861974644655
141 69707555825320
142 73748186278803
143 77992285211016
144 82448571697416
145 87126074804028
146 92034140659656
147 97182443029729
148 102580990675753
149 108240138363150
150 114170594547425
151 120383432828450
152 126890099939400
153 133702427692526
154 140832641279450
155 148293371687461
156 156097664353631
157 164258992064596
158 172791263938189
159 181708838854960
160 191026534776258
161 200759642684280
162 210923936282160
163 221535686456019
164 232611671328291
165 244169191293346
166 256226079433327
167 268800717101784
168 281912044750784
169 295579578076538
170 309823419226440
171 324664273561685
172 340123461253853
173 356222934636496
174 372985290243341
175 390433786763338
176 408592357486456
177 427485628920724
178 447138933655578
179 467578329610305
180 488830613370435
181 510923340082590
182 533884837227105
183 557744225221456
184 582531431639410
185 608277212489766
186 635013166941056
187 662771759291111
188 691586334157599
189 721491139204340
190 752521340808323
191 784713047506720
192 818103326203040
193 852730226350864
194 888632796656416
195 925851110068801
196 964426280989977
197 1004400491032554
198 1045817006803569
199 1088720206446378
200 1133155597952400
201 1179169846560850
202 1226810793609778
203 1276127484751701
204 1327170189414191
205 1379990429848448
206 1434641001150381
207 1491176001219944
208 1549650851354378
209 1610122327073260
210 1672648579358120
211 1737289166360755
212 1804105075236835
213 1873158754819486
214 1944514138058895
215 2018236675612896
216 2094393358970856
217 2173052754979326
218 2254285029594384
219 2338161983428645
220 2424757076144413
221 2514145462970460
222 2606404019818445
223 2701611380788034
224 2799847963947216
225 2901196009916456
226 3005739608325602
227 3113564737422049
228 3224759291290979
229 3339413120506618
230 3457618060052785
231 3579467971112440
232 3705058769701578
233 3834488469538506
234 3967857211482216
235 4105267307500983
236 4246823270848431
237 4392631861231264
238 4542802115736403
239 4697445395135640
240 4856675415659480
241 5020608296458820
242 5189362592154840
243 5363059341562241
244 5541822101028905
245 5725776994354726
246 5915052747021281
247 6109780737326866
248 6310095031431544
249 6516132435817750
250 6728032533164778
251 6945937736065125
252 7169993323833375
253 7400347497499404
254 7637151417472941
255 7880559259927936
256 8130728255337202
257 8387818746174144
258 8651994226427264
259 8923421400640883
260 9202270224326595
261 9488713964462330
262 9782929240815503
263 10085096087822536
264 10395397996938416
265 10714021979918818
266 11041158612108856
267 11377002097252309
268 11721750311734653
269 12075604870837320
270 12438771174054765
271 12811458472816410
272 13193879916786120
273 13586252623181596
274 13988797724071690
275 14401740437206881
276 14825310114439331
277 15259740314087606
278 15705268850383329
279 16162137867505280
280 16630593890068418
281 17110887898736590
282 17603275381884080
283 18108016412810599
284 18625375702474591
285 19155622678451116
286 19699031538753027
287 20255881332436464
288 20826456014645424
289 21411044528889048
290 22009940863204080
291 22623444134250145
292 23251858644606553
293 23895493968585666
294 24554665010805041
295 25229692093743578
296 25920901017478656
297 26628623149136954
298 27353195483813378
299 28094960735811925
300 28854267400892975
301 29631469849329400
302 30426928389366925
303 31241009362253176
304 32074085206928250
305 32926534556917236
306 33798742306403256
307 34691099709009171
308 35604004445132739
309 36537860722781110
310 37493079346185583
311 38470077818574480
312 39469280412225560
313 40491118273203494
314 41536029492724416
315 42604459214027621
316 43696859705070077
317 44813690467412884
318 45955418310409709
319 47122517462134738
320 48315469644934240
321 49534764188571760
322 50780898107160978
323 52054376214403521
324 53355711202073091
325 54685423757373138
326 56044042642836081
327 57432104815982824
328 58850155510655578
329 60298748358849330
330 61778445473654360
331 63289817573287415
332 64833444065502255
333 66409913174008856
334 68019822024370835
335 69663776772677416
336 71342392693110056
337 73056294308895436
338 74806115481394024
339 76592499543528865
340 78416099390415273
341 80277577615124670
342 82177606601044065
343 84116868660003714
344 86096056126213416
345 88115871496955326
346 90177027528116602
347 92280247377301029
348 94426264701153119
349 96615823800917828
350 98849679721397325
351 101128598399166800
352 103453356763183778
353 105824742885507976
354 108243556083764816
355 110710607074399123
356 113226718076828131
357 115792722969443794
358 118409467395475503
359 121077808921583160
360 123798617145637920
361 126572773857936330
362 129401173150728360
363 132284721582274261
364 135224338288140445
365 138220955147935296
366 141275516898587981
367 144388981303794026
368 147562319269100184
369 150796515014288420
370 154092566190287738
371 157451484054326785
372 160874293588894595
373 164362033679693134
374 167915757236463841
375 171536531373975856
376 175225437534739602
377 178983571672854774
378 182812044378839904
379 186711981066371943
380 190684522099042335
381 194730822980231140
382 198852054481811203
383 203049402836974656
384 207324069871121216
385 211677273197669408
386 216110246350933056
387 220624238985167489
388 225220517009456153
389 229900362789803290
390 234665075286273905
391 239515970258165770
392 244454380403200240
393 249481655566031266
394 254599162879509330
395 259808286976332501
396 265110430132634031
397 270507012482808816
398 275999472165215469
399 281589265540443400
400 287277867339151978
401 293066770883576700
402 298957488237763400
403 304951550432347379
404 311050507616966691
405 317255929288587086
406 323569404446117327
407 329992541822071744
408 336526970039653064
409 343174337847786958
410 349936314280449520
411 356814588895354405
412 363810871935548253
413 370926894571535436
414 378164409065414541
415 385525189016475618
416 393011029527647856
417 400623747454857784
418 408365181575811778
419 416237192842893345
420 424241664554561315
421 432380502611821610
422 440655635692004145
423 449069015509105496
424 457622616989968490
425 466318438538266906
426 475158502213376456
427 484144853998037431
428 493279563979672879
429 502564726622033680
430 512002460948988243
431 521594910819914040
432 531344245116255480
433 541252658020698324
434 551322369206244216
435 561555624119480641
436 571954694172196777
437 582521877028505814
438 593259496799306849
439 604169904333296498
440 615255477414017880
441 626518621055082470
442 637961767699831178
443 649587377520515941
444 661397938620885791
445 673395967339365628
446 685584008454300781
447 697964635491462304
448 710540450931975378
449 723314086523893200
450 736288203493130400
451 749465492859143475
452 762848675648595075
453 776440503215478826
454 790243757457540175
455 804261251140580136
456 818495828117962256
457 832950363659133746
458 847627764671936664
459 862530970035692885
460 877662950826345533
461 893026710653834680
462 908625285890407085
463 924461746012321594
464 940539193831037416
465 956860765839604396
466 973429632446756202
467 990248998327704609
468 1007322102661484259
469 1024652219486190438
470 1042242657939277665
471 1060096762617604960
472 1078217913820714978
473 1096609527915398046
474 1115275057582307216
475 1134217992185081063
476 1153441858019988831
477 1172950218689984924
478 1192746675357411203
479 1212834867122686480
480 1233218471280430160
481 1253901203702827240
482 1274886819098859280
483 1296179111402726881
484 1317781914036215385
485 1339699100301870066
486 1361934583648869681
487 1384492318070995386
488 1407376298375689824
489 1430590560587210890
490 1454139182218904098
491 1478026282681228245
492 1502256023557623215
493 1526832609017449064
494 1551760286095118541
495 1577043345108349976
496 1602686119940592602
497 1628692988464272004
498 1655068372826899544
499 1681816739879352403
500 1708942601465327875
501 1736450514855067750
502 1764345083038185903
503 1792630955162507376
504 1821312826830669816
505 1850395440544119798
506 1879883586003140256
507 1909782100556423269
508 1940095869504552253
509 1970829826554813060
510 2001988954128540845
511 2033578283821212530
512 2065602896713301760
513 2098067923836081536
514 2130978546486016370
515 2164339996695928321
516 2198157557553345731
517 2232436563677076226
518 2267182401539146609
519 2302400509947221320
520 2338096380370162938
521 2374275557425940610
522 2410943639211240120
523 2448106277794906359
524 2485769179551228591
525 2523938105659365256
526 2562618872440334227
527 2601817351862055624
528 2641539471880485704
529 2681791216950322268
530 2722578628369898760
531 2763907804798010465
532 2805784902602598953
533 2848216136383325806
534 2891207779324495841
535 2934766163723423458
536 2978897681347202056
537 3023608783967331214
538 3068905983720362778
539 3114795853648406565
540 3161285028064111455
541 3208380203097095220
542 3256088137062858765
543 3304415651015618416
544 3353369629121184130
545 3402957019215802776
546 3453184833183468656
547 3504060147520823891
548 3555590103718490019
549 3607781908832514050
550 3660642835869752303
551 3714180224365461400
552 3768401480773212800
553 3823314079048675354
554 3878925561043639816
555 3935243537096491861
556 3992275686430378077
557 4050029757749959344
558 4108513569644206989
559 4167735011189483658
560 4227702042356539320
561 4288422694620428980
562 4349905071371740378
563 4412157348532928961
564 4475187774974276291
565 4539004673136689918
566 4603616439451952481
567 4669031544972506384
568 4735258535796025778
569 4802306033701756870
570 4870182736579922240
571 4938897419074664935
572 5008458933017835295
573 5078876208079069396
574 5150158252203990915
575 5222314152270985056
576 5295353074534335456
577 5369284265287742256
578 5444117051311934304
579 5519860840545472705
580 5596525122536871193
581 5674119469122236490
582 5752653534882427505
583 5832137057827581674
584 5912579859858843216
585 5993991847460327666
586 6076383012165452402
587 6159763431255880789
588 6244143268232996399
589 6329532773523876448
590 6415942284957429805
591 6503382228477962920
592 6591863118626015178
593 6681395559259048716
594 6771990244037533416
595 6863657957152810803
596 6956409573817938531
597 7050256061003302654
598 7145208477932255503
599 7241277976823997600
600 7338475803394572200
601 7436813297607067550
602 7536301894177467600
603 7636953123332760101
604 7738778611321677725
605 7841790081180223036
606 7945999353247874381
607 8051418345940578946
608 8158059076271912464
609 8265933660634137160
610 8375054315324349858
611 8485433357333105505
612 8597083204876139235
613 8710016378190607194
614 8824245500071861041
615 8939783296677914296
616 9056642598071304202
617 9174836339031273834
618 9294377559601318184
619 9415279405909134263
620 9537555130719319215
621 9661218094261708160
622 9786281764789259603
623 9912759719414260696
624 10040665644672008216
625 10170013337364933988
626 10300816705131538456
627 10433089767299067649
628 10566846655457734953
629 10702101614321418630
630 10838869002307791585
631 10977163292407092690
632 11116999072767610680
633 11258391047573172406
634 11401354037634016810
635 11545902981272458341
636 11692052934919782431
637 11839819074010137836
638 11989216693582888749
639 12140261209185391040
640 12292968157480837298
641 12447353197159364320
642 12603432109552034240
643 12761220799550327539
644 12920735296225684291
645 13081991753758049626
646 13245006452061011727
647 13409795797718836104
648 13576376324617855344
649 13744764694892046978
650 13914977699560087800
651 14087032259480154325
652 14260945425992678653
653 14436734381883796776
654 14614416442034472941
655 14794009054392651098
656 14975529800628149256
657 15158996397114205244
658 15344426695588178378
659 15531838684141903585
660 15721250487888879395
661 15912680369963486230
662 16106146732194050785
663 16301668116111631936
664 16499263203628999170
665 16698950818058388846
666 16900749924797087856
667 17104679632354216551
668 17310759193042296159
669 17519008004013774220
670 17729445607958613763
671 17942091694149952560
672 18156966099148417520
673 18374088807856974584
674 18593479954231335216
675 18815159822344725281
676 19039148847104421977
677 19265467615325821474
678 19494136866455822129
679 19725177493656248218
680 19958610544533434560
681 20194457222231747290
682 20432738886169408578
683 20673477053141482581
684 20916693398062668591
685 21162409755079810008
686 21410648118320999181
687 21661430643018363064
688 21914779646263518778
689 22170717608139992340
690 22429267172485765880
691 22690451148035387795
692 22954292509188942915
693 23220814397164620566
694 23490040120774147055
695 23761993157585156176
696 24036697154703837656
697 24314175929947168966
698 24594453472632098944
699 24877553944758420325
700 25163501681804528253
701 25452321193920266100
702 25744037166730025325
703 26038674462535623954
704 26336258121126054816
705 26636813360991189136
706 26940365580138213202
707 27246940357315477569
708 27556563452836401539
709 27869260809813527858
710 28185058554989189745
711 28503982999980576680
712 28826060642117204378
713 29151318165696299986
714 29479782442827867416
715 29811480534700452343
716 30146439692433085231
717 30484687358352244984
718 30826251166850720403
719 31171158945675068520
720 31519438716792200040
721 31871118697687393260
722 32226227302237873320
723 32584793142022213921
724 32946845027200951465
725 33312411967836658206
726 33681523174782410081
727 34054208061012592706
728 34430496242518480104
729 34810417539650619230
730 35194001978021561018
731 35581279789859094565
732 35972281414916962655
733 36367037501839007524
734 36765578909077115341
735 37167936706267132816
736 37574142175154082402
737 37984226810979108264
738 38398222323412807824
739 38816160637953269523
740 39238073896866752355
741 39663994460597688370
742 40093954908716752303
743 40527988041342074616
744 40966126880095560416
745 41408404669535375978
746 41854854878119735656
747 42305511199651548629
748 42760407554249716253
749 43219578089805172000
750 43683057182960562125
751 44150879440577742250
752 44623079700725047000
753 45099693034157143876
754 45580754745309934650
755 46066300373791986561
756 46556365695387952131
757 47050986723561641646
758 47550199710467153889
759 48054041148464504560
760 48562547771138511058
761 49075756554826183830
762 49593704719644265760
763 50116429731028450919
764 50643969300768757791
765 51176361388561504196
766 51713644203052557827
767 52255856203401261184
768 52803036100332473984
769 53355222857712513088
770 53912455693609152640
771 54474774081880521985
772 55042217753243107353
773 55614826696872788346
774 56192641161481769841
775 56775701656931822538
776 57364048955319297456
777 57957724092601527874
778 58556768369689970578
779 59161223354088936405
780 59771130880997801135
781 60386533054962130640
782 61007472250984100205
783 61633991116186986056
784 62266132570933837610
785 62903939810504489116
786 63547456306223442056
787 64196725807149463411
788 64851792341211803299
789 65512700216913366190
790 66179494024475308623
791 66852218637552923520
792 67530919214389589640
793 68215641199545436014
794 68906430325059754416
795 69603332612193444901
796 70306394372599936477
797 71015662210080540204
798 71731183021764864269
799 72453003999879142178
800 73181172632935239600
801 73915736707512973400
802 74656744309457755778
803 75404243825676016801
804 76158283945342486691
805 76918913661708789898
806 77686182273319448881
807 78460139385834680344
808 79240834913255166378
809 80028319079758151610
810 80822642420931997320
811 81623855785625648055
812 82432010337192037935
813 83247157555351972336
814 84069349237446432595
815 84898637500313957496
816 85735074781552876856
817 86578713841412261876
818 87429607764063142584
819 88287809959504087745
820 89153374164841452713
821 90026354446208659510
822 90906805200056520545
823 91794781155086288434
824 92690337373549096216
825 93593529253193852806
826 94504412528575846602
827 95423043273018542949
828 96349477899932411679
829 97283773164790696668
830 98225986166457493485
831 99176174349178582240
832 100134395503918802578
833 101100707770366991856
834 102075169638283733216
835 103057839949520469683
836 104048777899376636931
837 105048043038634059914
838 106055695274923517903
839 107071794874773451240
840 108096402464987049680
841 109129579034705340370
842 110171385936793796440
843 111221884889920928341
844 112281137979954460605
845 113349207662054439576
846 114426156762080084781
847 115512048478697484666
848 116606946384796104744
849 117710914429612209100
850 118824016940155073578
851 119946318623345131425
852 121077884567451013475
853 122218780244242490054
854 123369071510437305441
855 124528824609870069536
856 125698106174948935202
857 126876983228839423294
858 128065523186932080464
859 129263793859041310183
860 130471863450882963295
861 131689800566289344380
862 132917674208696784003
863 134155553783375789136
864 135403509098929750416
865 136661610369540309768
866 137929928216476139856
867 139208533670354714209
868 140497498172661208153
869 141796893578025625170
870 143106792155752988465
871 144427266592115897210
872 145758389991894930720
873 147100235880687835946
874 148452878206460193890
875 149816391341870176981
876 151190850085830662831
877 152576329665849635656
878 153972905739602654029
879 155380654397290113880
880 156799652163220120218
881 158229975998181535140
882 159671703301038454680
883 161124911911119116499
884 162589680109820873091
885 164066086623016192966
886 165554210622668180527
887 167054131729252578864
888 168565930013385053624
889 170089685998259272598
890 171625480661284829280
891 173173395436542649445
892 174733512216433605053
893 176305913354150140516
894 177890681665336810541
895 179487900430578201778
896 181097653397070254656
897 182720024781125747104
898 184355099269856451378
899 186002962023695057025
900 187663698678089412675
901 189337395346040964450
902 191024138619809927025
903 192724015573471520776
904 194437113764632123450
905 196163521237002167586
906 197903326522124539256
907 199656618641964212471
908 201423487110647723439
909 203204021937070841960
910 204998313626649172883
911 206806453183942710280
912 208628532114418849160
913 210464642427093899644
914 212314876636307321416
915 214179327764381514721
916 216058089343407329577
917 217951255417920963534
918 219858920546702045409
919 221781179805467717538
920 223718128788682090440
921 225669863612268843310
922 227636480915432101978
923 229618077863386371621
924 231614752149190154591
925 233626601996493293588
926 235653726161382109581
927 237696223935145506224
928 239754195146131680578
929 241827740162531786680
930 243916959894249552560
931 246021955795702581715
932 248142829867703640355
933 250279684660280964706
934 252432623274571271535
935 254601749365657853016
936 256787167144476661056
937 258988981380672268986
938 261207297404515777224
939 263442221109780026965
940 265693858955669380573
941 267962317969712952720
942 270247705749707633165
943 272550130466629415114
944 274869700866588391416
945 277206526273759582676
946 279560716592349960602
947 281932382309547524929
948 284321634497501738819
949 286728584816290934878
950 289153345515914877025
951 291596029439281915600
952 294056750024213729778
953 296535621306450964326
954 299032757921671554816
955 301548275108514926823
956 304082288710612601631
957 306634915179632395444
958 309206271577321360003
959 311796475578568697760
960 314405645473462457120
961 317033900170371244880
962 319681359198013356960
963 322348142708558743361
964 325034371479710629145
965 327740166917826431146
966 330465651060013306481
967 333210946577268102826
968 335976176776585498384
969 338761465604118458770
970 341566937647299023538
971 344392718138017952085
972 347238932954759611695
973 350105708625800894784
974 352993172331358855341
975 355901451906810388456
976 358830675844852670602
977 361780973298742266924
978 364752474084469848104
979 367745308684018808243
980 370759608247552888035
981 373795504596695812190
982 376853130226731874703
983 379932618309905244256
984 383034102697635002216
985 386157717923834199358
986 389303599207137959056
987 392471882454243812389
988 395662704262152922653
989 398876201921530330140
990 402112513418960806605
991 405371777440329093570
992 408654133373088981840
993 411959721309665088616
994 415288682049735218530
995 418641157103652293601
996 422017288694741522531
997 425417219762742567866
998 428841093966120101169
999 432289055685527771000
1000 435761250026132200778