1 1
2 15
3 111
4 561
5 2211
6 7293
7 21021
8 54483
9 129558
10 286858
11 598026
12 1184118
13 2242266
14 4083366
15 7184166
16 12257850
17 20348031
18 32951985
19 52179985
20 80958735
21 123288165
22 184562235
23 271965915
24 394962165
25 565884540
26 800652996
27 1119632580
28 1548656956
29 2120241156
30 2875010556
31 3863375868
32 5147486916
33 6803501133
34 8924206083
35 11622038883
36 15032549181
37 19318356343
38 24673655721
39 31329333321
40 39558752871
41 49684284210
42 62084647086
43 77203149870
44 95556908370
45 117747135870
46 144470601730
47 176532362370
48 214859875230
49 260518613355
50 314729305605
51 378886935141
52 454581636795
53 543621642201
54 648058430151
55 770214248551
56 912712183593
57 1078508961336
58 1270930676808
59 1493711656008
60 1751036666808
61 2047586705736
62 2388588598968
63 2779868667576
64 3227910719176
65 3739918640601
66 4323883879095
67 4988658112791
68 5744031424905
69 6600816310155
70 7570937856405
71 8667530459445
72 9905041444155
73 11299341981070
74 12867845703570
75 14629635447570
76 16605598552686
77 18818571181410
78 21293492130846
79 24057566630046
80 27140440634946
81 30574386152343
82 34394498144281
83 38638903584633
84 43348983260583
85 48569606933133
86 54349382492691
87 60740919768243
88 67801109671581
89 75591419381556
90 84178204297356
91 93633037514380
92 104033057601396
93 115461335483340
94 128007261260340
95 141766951820340
96 156843680130060
97 173348327116965
98 191399857083435
99 211125817623435
100 232662865041685
101 256157316305631
102 281765728591425
103 309655507516641
104 340005545184591
105 373006889197866
106 408863443832118
107 447792704595126
108 490026527430858
109 535811933863558
110 585411953412858
111 639106504647546
112 697193316282918
113 759988889764611
114 827829504820461
115 901072269501261
116 980096216271315
117 1065303445750401
118 1157120319750175
119 1255998705290175
120 1362417271321425
121 1476882839929200
122 1599931793830800
123 1732131542029200
124 1874082045529200
125 2026417405069200
126 2189807512868976
127 2364959770441840
128 2552620874568336
129 2753578673578161
130 2968664096137311
131 3198753154788543
132 3444769026545121
133 3707684212890483
134 3988522781589933
135 4288362692774733
136 4608338211814051
137 4949642411546118
138 5313529766496666
139 5701318841770266
140 6114395079358566
141 6554213684668650
142 7022302616134806
143 7520265680837910
144 8049785739118410
145 8612628021231535
146 9210643559156865
147 9845772736738785
148 10520048961399615
149 11235602460733365
150 11994664207355115
151 12799569975448971
152 13652764532526405
153 14556805969976556
154 15514370176060756
155 16528255455075156
156 17601387296477868
157 18736823297850516
158 19937758245638508
159 21207529357689708
160 22549621691687508
161 23967673723651581
162 25465483100757843
163 27047012572808371
164 28716396106762221
165 30477945188819271
166 32336155318631385
167 34295712700298361
168 36361501134890295
169 38538609119323170
170 40832337156500670
171 43248205281722430
172 45791960810447170
173 48469586312588430
174 51287307818610930
175 54251603262786930
176 57369211169064366
177 60647139585091995
178 64092675270041301
179 67713393141960501
180 71517165990492651
181 75512174460887593
182 79706917315336311
183 84110221977756183
184 88731255368256633
185 93579535033616808
186 98664940580210136
187 103997725415914968
188 109588528807655976
189 115448388261327576
190 121588752230958376
191 128021493164084520
192 134758920890409816
193 141813796360941705
194 149199345744904455
195 156929274891844455
196 165017784166457145
197 173479583663780955
198 182329908812520645
199 191584536374380645
200 201259800847408395
201 211372611281468286
202 221940468514088610
203 232981482835046946
204 244514392088183646
205 256558580219058546
206 269134096277192718
207 282261673881765006
208 295962751159762258
209 310259491165712583
210 325174802792262633
211 340732362180992841
212 356956634642998743
213 373872897098901981
214 391507261048091331
215 409886696077132131
216 429039053917421805
217 448993093062309796
218 469778503954042140
219 491425934751034140
220 513967017686119140
221 537434396026567260
222 561861751646815140
223 587283833224996260
224 613736485074511260
225 641256676622028885
226 669882532543460731
227 699653363569606875
228 730609697973324741
229 762793313750230191
230 796247271505097841
231 831015948056286993
232 867145070770680351
233 904681752641784858
234 943674528123807558
235 984173389734684358
236 1026229825441205946
237 1069896856839552918
238 1115229078144721386
239 1162282696002490986
240 1211115570137759286
241 1261787254853240115
242 1314359041392698301
243 1368894001183069725
244 1425457029969993475
245 1484114892861462225
246 1544936270294477775
247 1607991804939780975
248 1673354149559909025
249 1741098015836018400
250 1811300224179098400
251 1884039754541388576
252 1959397798244003040
253 2037457810836955936
254 2118305566007975136
255 2202029210556685536
256 2288719320450939168
257 2378468957982266721
258 2471373730037623983
259 2567531847504807183
260 2667044185829113233
261 2770014346739024451
262 2876548721158902493
263 2986756553326882941
264 3100750006136370291
265 3218644227719742966
266 3340557419293089450
267 3466610904281009706
268 3596929198740730710
269 3731640083105001210
270 3870874675263448710
271 4014767505002301190
272 4163456589822597210
273 4317083512157230815
274 4475793498007402065
275 4639735497019270065
276 4809062264021833071
277 4983930442047289605
278 5164500646855365531
279 5350937552983324731
280 5543409981343615381
281 5742090988391339868
282 5947157956883974116
283 6158792688256001508
284 6377181496631367708
285 6602515304496905508
286 6834989740060123356
287 7074805236314997468
288 7322167131839655396
289 7577285773350088621
290 7840376620034283171
291 8111660349691410435
292 8391362966700975261
293 8679715911847075095
294 8976956174023182345
295 9283326403843122345
296 9599075029184181255
297 9924456372688541970
298 10259730771249511630
299 10605164697509271630
300 10961030883395150130
301 11327608445721687966
302 11705183013886041570
303 12094046859684541026
304 12494499029278497726
305 12906845477337634251
306 13331399203389789093
307 13768480390405830661
308 14218416545648998683
309 14681542643818176633
310 15158201272514886183
311 15648742780064083911
312 16153525425719131593
313 16672915532281604376
314 17207287641166895976
315 17757024669946876776
316 18322518072401159320
317 18904168001108826216
318 19502383472612777880
319 20117582535189161880
320 20750192439254651880
321 21400649810444652345
322 22069400825395815255
323 22756901390266567095
324 23463617322029658345
325 24190024532571063595
326 24936609215629878261
327 25703868036614177685
328 26492308325328126171
329 27302448271645947246
330 28134817124168692146
331 28989955391900071218
332 29868415048977942606
333 30770759742498384258
334 31697565003469608958
335 32649418460933317758
336 33626920059291424866
337 34630682278876426743
338 35661330359804029881
339 36719502529146995481
340 37805850231469505031
341 38921038362761698605
342 40065745507814387571
343 41240664181074295315
344 42446501071020533565
345 43683977288103377940
346 44953828616286764460
347 46256805768236288940
348 47593674644194853460
349 48965216594588468460
350 50372228686405085460
351 51815523973389703956
352 53295931770099366700
353 54814297929862030341
354 56371485126683673291
355 57968373141148379691
356 59605859150356517493
357 61284858021946509951
358 63006302612246083233
359 64771144068599258433
360 66580352135915743983
361 68434915467489774346
362 70335841940135832918
363 72284158973689091286
364 74280913854918793386
365 76327174065903211686
366 78424027616915203290
367 80572583383867796826
368 82773971450369646150
369 85029343454440594275
370 87339872939938000525
371 89706755712744895725
372 92131210201771444275
373 94614477824821608225
374 97157823359377326975
375 99762535318352946975
376 102429926330873058801
377 105161333528127324240
378 107958118934356303536
379 110821669863022722736
380 113753399318223053136
381 116754746401394709168
382 119827176723374607696
383 122972182821865270608
384 126191284584365093808
385 129486029676619849233
386 132857993976652932351
387 136308782014432315743
388 139840027417232619841
389 143453393360751164691
390 147150573026037321741
391 150933290062294942125
392 154803299055618097731
393 158762386003720833510
394 162812368796722094010
395 166955097704047454010
396 171192455867509752390
397 175526359800631200010
398 179958759894270006390
399 184491640928615046390
400 189127022591612566890
401 193866960003889414671
402 198713544250237750305
403 203668902917726698881
404 208735200640506876831
405 213914639651374224981
406 219209460340160071243
407 224621941819014842091
408 230154402494653340133
409 235809200647630005708
410 241588735018713083508
411 247495445402427120756
412 253531813247833731468
413 259700362266621071796
414 266003659048572984396
415 272444313684489285196
416 279024980396629183860
417 285748358176750349661
418 292617191431816657395
419 299634270637448173395
420 306802432999187469645
421 314124563121656884455
422 321603593685681881145
423 329242506133456191705
424 337044331361824970455
425 345012150423762723330
426 353149095238123321566
427 361458349307739954270
428 369943148445953422626
429 378606781511647729326
430 387452591152872470226
431 396483974559132091218
432 405704384222422631886
433 415117328707097138683
434 424726373428641494133
435 434535141441442974933
436 444547314235634420811
437 454766632543097467593
438 465196897152708872151
439 475841969734914533751
440 486705773675716395801
441 497792294920157994120
442 509105582825395002616
443 520649751023437714680
444 532428978293652988680
445 544447509445113778680
446 556709656208884966920
447 569219798140334812680
448 581982383531561932920
449 595001930334028333545
450 608283027091489616295
451 621830333883314095111
452 635648583278283167385
453 649742581298965899771
454 664117208396761405221
455 678777420437703207621
456 693728249699120412843
457 708974805877251130206
458 724522277105904216258
459 740375930986266043458
460 756541115627949629758
461 773023260701384101266
462 789827878501643099118
463 806960565023811383406
464 824427001049989531506
465 842232953248037275431
466 860384275282156672905
467 878886908935416959721
468 897746885244323586615
469 916970325645534602365
470 936563443134828206115
471 956532543438425956035
472 976884026196776788365
473 997624386160907670660
474 1018760214401447385660
475 1040298199530430617660
476 1062245128935990191556
477 1084607890030045995900
478 1107393471509099805316
479 1130608964628245904516
480 1154261564488508105916
481 1178358571337614445493
482 1202907391884321537051
483 1227915540626401263483
484 1253390641192403184933
485 1279340427697306747983
486 1305772746112178087121
487 1332695555647946919793
488 1360116930153419749311
489 1388045059527646305786
490 1416488251146756874086
491 1445454931305388879590
492 1474953646672821827226
493 1504993065763940416950
494 1535581980425146389450
495 1566729307335340389450
496 1598444089522095870550
497 1630735497893147805075
498 1663612832783319704925
499 1697085525517013204925
500 1731163139986385208675
501 1765855374245338348401
502 1801172062119451264815
503 1837123174831975970511
504 1873718822646030320961
505 1910969256523114380736
506 1948884869798080239168
507 1987476199870685599296
508 2026753929913862236608
509 2066728890598831199808
510 2107412061837197404608
511 2148814574540157053376
512 2190947712394952098368
513 2233822913658706754241
514 2277451772969781856591
515 2321846043176783657391
516 2367017637185364445425
517 2412978629822953180131
518 2459741259721555130685
519 2507317931218760318685
520 2555721216277101372435
521 2604963856421902213590
522 2655058764697759812810
523 2706019027643802070090
524 2757857907287865697590
525 2810588843159738808090
526 2864225454323613740646
527 2918781541429896486630
528 2974271088786519914106
529 3030708266449908826431
530 3088107432335745732081
531 3146483134349687046993
532 3205850112538180298191
533 3266223301259533748133
534 3327617831375390713083
535 3390049032462761705883
536 3453532435046768393781
537 3518083772854254225468
538 3583718985088417448196
539 3650454218724623105796
540 3718305830827551481596
541 3787290390889841326660
542 3857424683192387093436
543 3928725709186450277820
544 4001210689897745858820
545 4074897068352665714445
546 4149802512026801785155
547 4225944915315932652195
548 4303342402029638097405
549 4382013327907707113655
550 4461976283159505740905
551 4543250095026472012041
552 4625853830367906205095
553 4709806798270225514226
554 4795128552679853170926
555 4881838895059912969326
556 4969957877070901075218
557 5059505803275507927486
558 5150503233867763973058
559 5242970987426683912258
560 5336930143694585070558
561 5432402046380256455211
562 5529408305987156001093
563 5627970802666814459301
564 5728111689097625334651
565 5829853393389201234201
566 5933218622012477948295
567 6038230362755748548391
568 6144911887706810752105
569 6253286756261411775480
570 6363378818158175865480
571 6475212216540200682120
572 6588811391043509679480
573 6704201080912548618120
574 6821406328142915328120
575 6940452480651512832120
576 7061365195474316931336
577 7184170441991950354585
578 7308894505183256570871
579 7435563988907067370071
580 7564205819212359323721
581 7694847247676995248843
582 7827515854775247812181
583 7962239553274303430133
584 8099046591659945641083
585 8237965557591618151758
586 8379025381387068787666
587 8522255339536776609618
588 8667685058248365493806
589 8815344517021208511906
590 8965264052251428490206
591 9117474360867501172830
592 9272006503996668463746
593 9428891910662370275415
594 9588162381512904568665
595 9749850092581526228665
596 9913987599078196485735
597 10080607839213195657165
598 10249744138052813057235
599 10421430211407328997235
600 10595700169751504875485
601 10772588522177798439156
602 10952130180382522385100
603 11134360462685165555916
604 11319315098081097080116
605 11507030230327874901516
606 11697542422065381242868
607 11890888658970008652276
608 12087106353943121388108
609 12286233351334018008933
610 12488307931197622149483
611 12693368813587129581771
612 12901455162881840782293
613 13112606592150409351711
614 13326863167549737762561
615 13544265412759753043361
616 13764854313454296144015
617 13988671321808359867626
618 14215758361041911397750
619 14446157830000536597750
620 14679912607773144410250
621 14917066058346970839750
622 15157662035300123160250
623 15401744886531906152250
624 15649359459031173339750
625 15900551103682947367875
626 16155365680113554835501
627 16413849561574522074765
628 16676049639865479550611
629 16942013330296323738561
630 17211788576688886527711
631 17485423856418363388543
632 17762968185494752741521
633 18044471123684560162608
634 18329982779673022265808
635 18619553816267106310608
636 18913235455639542793776
637 19211079484614149500368
638 19513138259992706708016
639 19819464713923644461616
640 20130112359312804062416
641 20445135295276537146225
642 20764588212637406960031
643 21088526399462757684735
644 21417005746646418893985
645 21750082753533813485235
646 22087814533590738669165
647 22430258820116090857485
648 22777473971998806546915
649 23129518979519292558790
650 23486453470195620259290
651 23848337714674759654746
652 24215232632669130529830
653 24587199798938749073706
654 24964301449319249720406
655 25346600486796063214806
656 25734160487625033204618
657 26127045707499754951791
658 26525321087765921053633
659 26929052261682960364833
660 27338305560733257616383
661 27753148020979242536181
662 28173647389468638588843
663 28599872130688162768971
664 29031891433065969202821
665 29469775215523130637996
666 29913594134074453229460
667 30363419588478921362836
668 30819323728940070592620
669 31281379462856588113620
670 31749660461623441528620
671 32224241167483838023980
672 32705196800432317417620
673 33192603365169283900605
674 33686537658107282654355
675 34187077274429328890355
676 34694300615199598228141
677 35208286894526788700295
678 35729116146780466050201
679 36256869233860705369401
680 36791627852521343506551
681 37333474541747158069218
682 37882492690185290233086
683 38438766543631229970558
684 39002381212569683712258
685 39573422679770645860558
686 40151977807940996983986
687 40738134347431952935218
688 41331980944002690553326
689 41933607146640477033051
690 42543103415437631470101
691 43160561129525648521845
692 43786072595066815557291
693 44419731053303656108905
694 45061630688666533881655
695 45711866636939753021655
696 46370534993486491797945
697 47037732821532908306280
698 47713558160511758263320
699 48398110034465866423320
700 49091488460511794617320
701 49793794457364050886936
702 50505130053920185661160
703 51225598297907122405096
704 51955303264589071654296
705 52694350065537378837321
706 53442844857462657782343
707 54200894851109563301031
708 54968608320214557744633
709 55746094610527027933083
710 56533464148894110368133
711 57330828452409584155941
712 58138300137627192583243
713 58955992929838755814206
714 59784021672417438702306
715 60622502336226539243106
716 61471552029094164729630
717 62331289005354164212146
718 63201832675453687408590
719 64083303615627741760590
720 64975823577641120883090
721 65879515498598079212935
722 66794503510820129223465
723 67720912951792339138185
724 68658870374178510646935
725 69608503555905617702685
726 70569941510317889056131
727 71543314496400918768675
728 72528754029076190532141
729 73526392889566403215716
730 74536365135831986657116
731 75558806113079198315868
732 76593852464340193011876
733 77641642141125459582108
734 78702314414149019902308
735 79776009884126787339108
736 80862870492648483320796
737 81963039533123512342293
738 83076661661801197351611
739 84203882908865779101211
740 85344850689606584688261
741 86499713815663772152815
742 87668622506350059652401
743 88851728400048849385425
744 90049184565689158094175
745 91261145514297767641050
746 92487767210629010818950
747 93729207084872609228550
748 94985624044439981731450
749 96257178485829443668950
750 97544032306570718721450
751 98846348917249186973226
752 100164293253610294441590
753 101498031788744551028211
754 102847732545353545553661
755 104213565108097408244061
756 105595700636024152751043
757 106994311875081331503121
758 108409573170710439907983
759 109841660480524506651183
760 111290751387069309067233
761 112757025110668654294176
762 114240662522354168662368
763 115741846156880039512416
764 117260760225823155386016
765 118797590630769092286816
766 120352524976584395466400
767 121925752584775607953056
768 123517464506935498808160
769 125127853538276945866785
770 126757114231254929495535
771 128405442909277095681615
772 130073037680503348552785
773 131760098451734934218115
774 133466826942393479614365
775 135193426698590451842365
776 136940103107287505281971
777 138707063410548185583030
778 140494516719881461443306
779 142302674030677556902506
780 144131748236736558704406
781 145981954144890275106618
782 147853508489717824349766
783 149746629948355432834758
784 151661539155400924898458
785 153598458717913387924383
786 155557613230508498376081
787 157539229290549996196593
788 159543535513437796877871
789 161570762547993232369221
790 163621143091941913863771
791 165694911907494711376635
792 167792305837027346907861
793 169913563818859099867420
794 172058926903131125328420
795 174228638267784887568420
796 176422943234641213257180
797 178642089285580470552420
798 180886326078824382273180
799 183155905465319983233180
800 185451081505226233734180
801 187772110484503803141741
802 190119250931608539392995
803 192492763634289142218051
804 194892911656489559793501
805 197319960355356630488151
806 199774177398353493307593
807 202255832780479292595561
808 204765198841595704506183
809 207302550283860814722258
810 209868164189270878860558
811 212462320037310498975886
812 215085299722711751551218
813 217737387573322804341726
814 220418870368086561425826
815 223130037355129877806626
816 225871180269963886902270
817 228642593353795986263691
818 231444573371954028863205
819 234277419632423269307205
820 237141434004496616340955
821 240036920937538745033145
822 242964187479864624052455
823 245923543297733015477895
824 248915300694455506619145
825 251939774629621635362520
826 254997282738440672602536
827 258088145351200627368360
828 261212685512845042308696
829 264371229002668149257896
830 267564104354128956670296
831 270791642874784842778968
832 274054178666345230409256
833 277352048644845921456633
834 280685592560944671122583
835 284055153020338584091383
836 287461075504303916924841
837 290903708390358873051243
838 294383402973049978828981
839 297900513484862631274581
840 301455397117256410159131
841 305048414041825749296430
842 308679927431586563970546
843 312350303482389433579890
844 316059911434459940709390
845 319809123594066769981890
846 323598315355318172184510
847 327427865222087401315390
848 331298154830067734351010
849 335209568968957685694135
850 339162495604777030427385
851 343157325902314252667481
852 347194454247706037490375
853 351274278271149427077741
854 355397198869747263920691
855 359563620230487546107091
856 363773949853357321914493
857 368028598574591753131476
858 372327980590058978736108
859 376672513478781412771308
860 381062618226594112473108
861 385498719249940854929196
862 389981244419808562771668
863 394510625085800721639636
864 399087296100350434384236
865 403711695843073759230661
866 408384266245263981359115
867 413105452814527469619051
868 417875704659561772348725
869 422695474515076608534975
870 427565218766858412816225
871 432485397476979095105025
872 437456474409149677884975
873 442478917054219476520650
874 447553196655821490208150
875 452679788236164673488150
876 457859170621973760542826
877 463091826470577316802790
878 468378242296144694700186
879 473718908496072572719386
880 479114319377521759217286
881 484564973184104944811043
882 490071372122726089462221
883 495634022390572132722733
884 501253434202257717949683
885 506930121817123623643233
886 512664603566689597413951
887 518457401882262290443743
888 524309043322698992667441
889 530220058602327871270416
890 536190982619025417471216
891 542222354482451808937200
892 548314717542444897565456
893 554468619417573534750960
894 560684612023850948658960
895 566963251603608890418960
896 573305098754533268563440
897 579710718458861993445585
898 586180680112745755786815
899 592715557555772465926815
900 599315929100656082776065
901 605982377563090563903571
902 612715490291769670630605
903 619515859198573364444781
904 626384080788921533497731
905 633320756192295790404006
906 640326491192930085018618
907 647401896260670878335866
908 654547586582007626122758
909 661764182091274323376458
910 669052307502022863176758
911 676412592338568965991606
912 683845670967711437986218
913 691352182630625519384271
914 698932771474931086433121
915 706588086586936473033921
916 714318782024058680611935
917 722125516847420747322261
918 730008955154627050211595
919 737969766112717316487595
920 746008623991300122583845
921 754126208195866662250380
922 762323203301285567447220
923 770600299085479568371380
924 778958190563284781506380
925 787397578020493417147380
926 795919167048080700424716
927 804523668576616802423820
928 813211798910864580580276
929 821984279764563930115101
930 830841838295403550867251
931 839785207140180936477843
932 848815124450151395483661
933 857932333926566916486183
934 867137584856405692176633
935 876431632148293119617433
936 885815236368615096805911
937 895289163777824438177218
938 904854186366941234340126
939 914511081894247983981726
940 924260633922180328525026
941 934103631854414222777070
942 944040870973150377464466
943 954073152476596812218130
944 964201283516650360239630
945 974426077236777968557755
946 984748352810098640465845
947 995168935477666869418005
948 1005688656586958416355595
949 1016308353630559285134345
950 1027028870285058753427095
951 1037851056450147319187511
952 1048775768287920425476185
953 1059803868262388829172296
954 1070936225179196481821496
955 1082173714225546793603896
956 1093517217010338154144968
957 1104967621604509586636856
958 1116525822581597414488008
959 1128192721058503822475208
960 1139969224736478197134008
961 1151856247942312133891241
962 1163854711669749001216743
963 1175965543621108954850631
964 1188189678249130297947481
965 1200528056799028085769531
966 1212981627350770876357605
967 1225551344861576531410821
968 1238238171208627974414315
969 1251043075232009815868190
970 1263967032777866758290690
971 1277011026741784696494210
972 1290176047112395431464190
973 1303463091015205919008210
974 1316873162756652977185710
975 1330407273868384379377710
976 1344066443151767262710706
977 1357851696722624784409575
978 1371764068056201961520841
979 1385804598032361632320041
980 1399974334981011480595191
981 1414274334727763066882493
982 1428705660639823813620451
983 1443269383672122894084483
984 1457966582413671977865933
985 1472798343134161788567108
986 1487765759830795432297596
987 1502869934275359458476668
988 1518111976061533617372036
989 1533493002652440281736636
990 1549014139428434502842436
991 1564676519735135674153540
992 1580481284931701778830076
993 1596429584439347200209525
994 1612522575790105077373275
995 1628761424675835190873275
996 1645147304997478366666725
997 1661681398914558389285775
998 1678364896894932418254225
999 1695198997764790904754225
1000 1712184908758908008542975