0 1
1 3
2 44
3 361
4 2010
5 7952
6 25401
7 68662
8 164459
9 357241
10 718934
11 1357271
12 2431460
13 4164014
14 6864051
15 10942908
16 16946805
17 25576479
18 37731200
19 54532437
20 77381198
21 107985724
22 148434413
23 201227282
24 269366687
25 356392309
26 466492202
27 604540771
28 776232600
29 988122938
30 1247787111
31 1563862712
32 1946237289
33 2406091515
34 2956118228
35 3610565505
36 4385489986
37 5298798888
38 6370540961
39 7622946094
40 9080757075
41 10771265585
42 12724688382
43 14974198063
44 17556347084
45 20511091846
46 23882268443
47 27717608180
48 32069268701
49 36993839255
50 42552931368
51 48813171693
52 55846856118
53 63731928276
54 72552701525
55 82399820682
56 93371056007
57 105571245997
58 119113168082
59 134117459771
60 150713570432
61 169039658386
62 189243628751
63 211483003504
64 235926050001
65 262751621363
66 292150380924
67 324324609689
68 359489531562
69 397873084992
70 439717354505
71 485278303014
72 534827314747
73 588650885097
74 647052280742
75 710351183239
76 778885471668
77 853010816606
78 933102591363
79 1019555412268
80 1112785184069
81 1213228582927
82 1321345242320
83 1437617174405
84 1562551102238
85 1696677815660
86 1840554656445
87 1994764804098
88 2159919919983
89 2336659358949
90 2525652979322
91 2727600275475
92 2943233359976
93 3173316012778
94 3418646842679
95 3680058247976
96 3958419763769
97 4254636929515
98 4569654829604
99 4904456862385
100 5260068480786
101 5637555858008
102 6038029835889
103 6462644481566
104 6912601250595
105 7389147429537
106 7893580521806
107 8427246570207
108 8991544772764
109 9587925679926
110 10217896048619
111 10883016907876
112 11584908658605
113 12325249002119
114 13105778294136
115 13928297329693
116 14794672959110
117 15706835723524
118 16666785741605
119 17676590188922
120 18738389463383
121 19854394502429
122 21026893236258
123 22258247735787
124 23550900961872
125 24907373737794
126 26330271803807
127 27822282606816
128 29386182668705
129 31024834186723
130 32741192725196
131 34538303619017
132 36419309997434
133 38387448983920
134 40446060061913
135 42598581063190
136 44848556884491
137 47199635257433
138 49655575826166
139 52220245690679
140 54897628854660
141 57691821534990
142 60607041990227
143 63647625587868
144 66818035022869
145 70122855135231
146 73566803529248
147 77154725132725
148 80891603226606
149 84782553738140
150 88832836691853
151 93047850227698
152 97433142483263
153 101994405328981
154 106737486692810
155 111668384003267
156 116793256966712
157 122118420710042
158 127650359022087
159 133395717186456
160 139361315697417
161 145554142774491
162 151981368564596
163 158650337328609
164 165568582140386
165 172743816736648
166 180183950724929
167 187897081086734
168 195891507905267
169 204175725512977
170 212758438751390
171 221648553752719
172 230855194742892
173 240387694448102
174 250255611453627
175 260468720224724
176 271037029032573
177 281970769580151
178 293280415508168
179 304976671615053
180 317070492954454
181 329573073639732
182 342495866546165
183 355850571688810
184 369649156541223
185 383903843976845
186 398627133217650
187 413831787327643
188 429530854803488
189 445737656610034
190 462465808426607
191 479729207212880
192 497542054123121
193 515918840592083
194 534874371931164
195 554423752922361
196 574582412108874
197 595366086886560
198 616790848503209
199 638873086635270
200 661629535108571
201 685077255949513
202 709233665841734
203 734116519639271
204 759743937572180
205 786134388210622
206 813306716434211
207 841280125834252
208 870074207460069
209 899708921648111
210 930204627560304
211 961582064426981
212 993862381890750
213 1027067120651724
214 1061218243632221
215 1096338116010978
216 1132449537222415
217 1169575720368069
218 1207740325066010
219 1246967436225907
220 1287281597762568
221 1328707790722634
222 1371271467878103
223 1414998531190792
224 1459915367300057
225 1506048824312779
226 1553426248201412
227 1602075458905361
228 1652024787653810
229 1703303052366008
230 1755939595915281
231 1809964260813822
232 1865407428432579
233 1922299992957825
234 1980673401583598
235 2040559627725375
236 2101991212199996
237 2165001235683478
238 2229623360895371
239 2295891804285764
240 2363841379239245
241 2433507466977895
242 2504926060802072
243 2578133736194173
244 2653167696111654
245 2730065740278116
246 2808866311546053
247 2889608464359770
248 2972331912203511
249 3057076995222525
250 3143884728774338
251 3232796770192203
252 3323855468455408
253 3417103830081186
254 3512585569932095
255 3610345076220352
256 3710427462468417
257 3812878531611587
258 3917744829130092
259 4025073606233641
260 4134912874181402
261 4247311366534096
262 4362318594680441
263 4479984809140214
264 4600361056313771
265 4723499138821433
266 4849451673494934
267 4978272050736279
268 5110014493767972
269 5244734016996462
270 5382486486540275
271 5523328577580924
272 5667317836186037
273 5814512635632607
274 5964972239544512
275 6118756757170709
276 6275927207854478
277 6436545475251196
278 6600674373148973
279 6768377598608338
280 6939719799151839
281 7114766524810037
282 7293584296700010
283 7476240557959715
284 7662803743733208
285 7853343230977530
286 8047929409874855
287 8246633632493688
288 8449528285645993
289 8656686738386619
290 8868183416335892
291 9084093747998785
292 9304494240571266
293 9529462425062888
294 9759076933607649
295 9993417443371246
296 10232564755384979
297 10476600737221105
298 10725608403370814
299 10979671856668655
300 11238876370233356
301 11503308327624518
302 11773055306367579
303 12048206016823476
304 12328850387316765
305 12615079501701207
306 12906985686112616
307 13204662445210797
308 13508204550576374
309 13817707975611796
310 14133269985603989
311 14454989071264586
312 14782965040477895
313 15117298950462829
314 15458093201228306
315 15805451466336763
316 16159478788086720
317 16520281506860114
318 16887967358054415
319 17262645399993392
320 17644426112628753
321 18033421323996339
322 18429744310709948
323 18833509722942297
324 19244833686731242
325 19663833727467264
326 20090628874035017
327 20525339580786406
328 20968087833537915
329 21418997070010793
330 21878192287707366
331 22345799962797127
332 22821948159892724
333 23306766449363230
334 23800386019033283
335 24302939589902060
336 24814561529786501
337 25335387767427023
338 25865555908098576
339 26405205146081349
340 26954476382260830
341 27513512134944300
342 28082456659473917
343 28661455857366978
344 29250657397963439
345 29850210625870501
346 30460266684668858
347 31080978422639315
348 31712500518549416
349 32354989385642410
350 33008603299528823
351 33673502300415208
352 34349848323122553
353 35037805097534891
354 35737538280769380
355 36449215355821937
356 37173005765911122
357 37909080811300632
358 38657613785842097
359 39418779871951326
360 40192756279372387
361 40979722138287201
362 41779858640326286
363 42593348929788319
364 43420378246920156
365 44261133817225718
366 45115804997040939
367 45984583160908324
368 46867661849469677
369 47765236654885447
370 48677505371071160
371 49604667877137629
372 50546926289994182
373 51504484845788612
374 52477550054903397
375 53466330581371194
376 54471037400287383
377 55491883675179741
378 56529084917863778
379 57582858863742123
380 58653425634126224
381 59741007609443842
382 60845829594053855
383 61968118687337120
384 63108104451028193
385 64266018778167715
386 65442096062978060
387 66636573067652233
388 67849689094797498
389 69081685852038704
390 70332807627057177
391 71603301149983190
392 72893415771054411
393 74203403320775193
394 75533518290222134
395 76884017688944631
396 78255161227942084
397 79647211175283150
398 81060432541782419
399 82495092934312540
400 83951462744205141
401 85429814998233023
402 86930425549763424
403 88453572927384181
404 89999538528834350
405 91568606467251292
406 93161063767907021
407 94777200212049842
408 96417308536471679
409 98081684274920981
410 99770625960529674
411 101484434964770691
412 103223415702770040
413 104987875469785434
414 106778124649432391
415 108594476547657048
416 110437247603902025
417 112306757222549659
418 114203327987056820
419 116127285488841377
420 118078958544411938
421 120058679021673544
422 122066782060081793
423 124103605894340302
424 126169492077605427
425 128264785302551249
426 130389833627654622
427 132544988295599951
428 134730603962671020
429 136947038514471078
430 139194653298451451
431 141473812936918932
432 143784885562727869
433 146128242629550135
434 148504259150760968
435 150913313506943245
436 153355787687994006
437 155832067097838068
438 158342540799785781
439 160887601318427434
440 163467644888269415
441 166083071252784205
442 168734283916355762
443 171421689940456283
444 174145700198928224
445 176906729171262386
446 179705195201247663
447 182541520287321360
448 185416130344614321
449 188329454992347795
450 191281927819305308
451 194273986168246713
452 197306071404834698
453 200378628699040096
454 203492107297554665
455 206646960302158022
456 209843644945644827
457 213082622367127177
458 216364357891508102
459 219689320801689511
460 223057984621620372
461 226470826885383806
462 229928329423852131
463 233430978130622924
464 236979263252309541
465 240573679151299503
466 244214724599712944
467 247902902538952869
468 251638720377360382
469 255422689746529932
470 259255326802694045
471 263137151979772834
472 267068690294517327
473 271050471096266117
474 275083028375880282
475 279166900512176179
476 283302630584681288
477 287490766116715786
478 291731859392002583
479 296026467194366408
480 300375151128227609
481 304778477354891147
482 309237016916957700
483 313751345471171025
484 318322043616776178
485 322949696624897400
486 327634894770877265
487 332378233060153278
488 337180311564608003
489 342041735144916289
490 346963113790940462
491 351945062340516095
492 356988200823922556
493 362093154179078998
494 367260552600124619
495 372491031248992516
496 377785230608130189
497 383143796188422695
498 388567378886088024
499 394056634686916925
500 399612225027373926
501 405234816495125028
502 410925081194379269
503 416683696442671386
504 422511345140474935
505 428408715464210877
506 434376501240167426
507 440415401633701387
508 446526121527495984
509 452709371206925666
510 458965866742687359
511 465296329672295296
512 471701487387117185
513 478182072809969539
514 484738824786594476
515 491372487759321833
516 498083812163018330
517 504873554094786704
518 511742475714423225
519 518691344910119862
520 525720935703462123
521 532832027911104249
522 540025407554343638
523 547301866516734807
524 554662202958272612
525 562107220968914734
526 569637730987410227
527 577254549450695996
528 584958499217403125
529 592750409213096863
530 600631114858497536
531 608601457710529237
532 616662285895288014
533 624814453744868540
534 633058822235116653
535 641396258618198930
536 649827636865172511
537 658353837294266613
538 666975747018306986
539 675694259568674019
540 684510275347615000
541 693424701247847610
542 702438451109797607
543 711552445336812088
544 720767611357356009
545 730084883235803771
546 739505202139632468
547 749029515945755905
548 758658779712748226
549 768393955282688680
550 778236011758453793
551 788185925101036718
552 798244678611941843
553 808413262525946801
554 818692674498637950
555 829083919194578607
556 839588008780019532
557 850205962506441222
558 860938807208478107
559 871787576882798196
560 882753313191275357
561 893837065035173911
562 905039889063607976
563 916362849242994029
564 927807017370831926
565 939373472640392788
566 951063302159860949
567 962877600512219914
568 974817470279790087
569 986884021599279917
570 999078372691758930
571 1011401649412836539
572 1023854985788105472
573 1036439523558415122
574 1049156412720825167
575 1062006811068935664
576 1074991884739386193
577 1088112807747209331
578 1101370762537915388
579 1114766939517831193
580 1128302537611805994
581 1141978763788501952
582 1155796833623761545
583 1169757970820811430
584 1183863407779327163
585 1198114385110516585
586 1212512152211922470
587 1227057966777346823
588 1241753095377427508
589 1256598812964369374
590 1271596403458335747
591 1286747159246947500
592 1302052381777525701
593 1317513381051324303
594 1333131476221665104
595 1348907995082864901
596 1364844274674299294
597 1380941660763989740
598 1397201508458637629
599 1413625181681831810
600 1430214053790089711
601 1446969507045650533
602 1463892933238565114
603 1480985733154035091
604 1498249317200588520
605 1515685104871929962
606 1533294525381243831
607 1551079017117515432
608 1569040028285999289
609 1587179016358975851
610 1605497448722427044
611 1623996802121188401
612 1642678563311869330
613 1661544228502365144
614 1680595304011064561
615 1699833305700681118
616 1719259759643785635
617 1738876201550921249
618 1758684177442503630
619 1778685243071178847
620 1798880964600129308
621 1819272918019638454
622 1839862689831845483
623 1860651876461475812
624 1881642084947082797
625 1902834932345907719
626 1924232046431651832
627 1945835065093424541
628 1967645637040084230
629 1989665421193238148
630 2011896087398195621
631 2034339315810978042
632 2056996797615923159
633 2079870234406668445
634 2102961338910450338
635 2126271834363019115
636 2149803455239672016
637 2173557946624062658
638 2197537064946012191
639 2221742577344171104
640 2246176262410647585
641 2270839909547484515
642 2295735319718149452
643 2320864304797784393
644 2346228688331596794
645 2371830304878844656
646 2397671000778173273
647 2423752633485292950
648 2450077072345301131
649 2476646197924015065
650 2503461902787324278
651 2530526090826135223
652 2557840678042793988
653 2585407591869605006
654 2613228771962369235
655 2641306169512433692
656 2669641748047385237
657 2698237482736592767
658 2727095361199102112
659 2756217382802627381
660 2785605559478687342
661 2815261915015007516
662 2845188485877943821
663 2875387320498251634
664 2905860480100837311
665 2936610037983855573
666 2967638080355834954
667 2998946705608059459
668 3030538025159108792
669 3062414162720485402
670 3094577255148615815
671 3127029451703678744
672 3159772914909108617
673 3192809819803585627
674 3226142354808088052
675 3259772720970999649
676 3293703132842752098
677 3327935817714010376
678 3362473016497952193
679 3397316982961486478
680 3432469984615211379
681 3467934301937626257
682 3503712229272815390
683 3539806074047608335
684 3576218157677031148
685 3612950814774375270
686 3650006394064463675
687 3687387257586582868
688 3725095781615606013
689 3763134355857747959
690 3801505384379593032
691 3840211284796627405
692 3879254489210213846
693 3918637443388861108
694 3958362607713193589
695 3998432456349911786
696 4038849478204799399
697 4079616176089334285
698 4120735067681781234
699 4162208684686407195
700 4204039573802702496
701 4246230295877159538
702 4288783426880670959
703 4331701557052825296
704 4374987291887525105
705 4418643251269758547
706 4462672070469486236
707 4507076399270841977
708 4551858902974331594
709 4597022261518421536
710 4642569170490098729
711 4688502340238800006
712 4734824496895376475
713 4781538381478322249
714 4828646750921192646
715 4876152377171084903
716 4924058048224553940
717 4972366567218303294
718 5021080753473648035
719 5070203441579368332
720 5119737482444763493
721 5169685742374626159
722 5220051104130937328
723 5270836465999913317
724 5322044742862385982
725 5373678865252880204
726 5425741780438729437
727 5478236451471135586
728 5531165858273064335
729 5584532996682244933
730 5638340879547895706
731 5692592535765615347
732 5747291011382983304
733 5802439368626299850
734 5858040687015112023
735 5914098062380753800
736 5970614607989842521
737 6027593453554576203
738 6085037746365251396
739 6142950650292268689
740 6201335346927717170
741 6260195034579044920
742 6319532929419761297
743 6379352264474723198
744 6439656290780000579
745 6500448276359735041
746 6561731507395220078
747 6623509287193282495
748 6685784937364623036
749 6748561796783676950
750 6811843222776266763
751 6875632590070892228
752 6939933291995741133
753 7004748739421364711
754 7070082361967098520
755 7135937606935073277
756 7202317940526091942
757 7269226846764931812
758 7336667828725730117
759 7404644407448527066
760 7473160123174206327
761 7542218534252234621
762 7611823218385209666
763 7681977771527745739
764 7752685809140675696
765 7823950965081037858
766 7895776892865984959
767 7968167264553821504
768 8041125772017666497
769 8114656125817496387
770 8188762056483614700
771 8263447313379649449
772 8338715665995876762
773 8414570902803127632
774 8491016832556018937
775 8568057283137718134
776 8645696102873129003
777 8723937159364468921
778 8802784340814462998
779 8882241554852682263
780 8962312729868793764
781 9043001813829614062
782 9124312775622469235
783 9206249603862911740
784 9288816308248238133
785 9372016918355823455
786 9455855485006850880
787 9540336079055211413
788 9625462792761493518
789 9711239738572402044
790 9797671050505062317
791 9884760882916905810
792 9972513411900336991
793 10060932834043039413
794 10150023367833060074
795 10239789252409483171
796 10330234748977980504
797 10421364139551806330
798 10513181728377868839
799 10605691840667993080
800 10698898824035562281
801 10792807047217002043
802 10887420901519046804
803 10982744799530392001
804 11078783176579634690
805 11175540489437046632
806 11273021217783244641
807 11371229862901031022
808 11470170949154842899
809 11569849022672612721
810 11670268652836052414
811 11771434430952480111
812 11873350971755988620
813 11976022912069190854
814 12079454912315328731
815 12183651655169883188
816 12288617847083673245
817 12394358216924282839
818 12500877517510206440
819 12608180524242038317
820 12716272036647714678
821 12825156877003417364
822 12934839891889969173
823 13045325950803397322
824 13156619947722532167
825 13268726799709182189
826 13381651448486993042
827 13495398859031179131
828 13609974021158693440
829 13725381948107467218
830 13841627678137947791
831 13958716273101791152
832 14076652820054818449
833 14195442429815112755
834 14315090238587451708
835 14435601406510752985
836 14556981119294034026
837 14679234586753157248
838 14802367044458374601
839 14926383752260316774
840 15051289995949173755
841 15177091085769878825
842 15303792358092983142
843 15431399173918978503
844 15559916920560917364
845 15689351010137824926
846 15819706881269122883
847 15950989997557074540
848 16083205849293063941
849 16216359951929024335
850 16350457847795631248
851 16485505104562657733
852 16621507316969133278
853 16758470105272575916
854 16896399116991175805
855 17035300025341847362
856 17175178530994489647
857 17316040360498808357
858 17457891268050712122
859 17600737033907847251
860 17744583466168182312
861 17889436399174205226
862 18035301695303755511
863 18182185243362826344
864 18330092960388697081
865 18479030790031289643
866 18629004704368660964
867 18780020702276856049
868 18932084811257813202
869 19085203085797662872
870 19239381609207105585
871 19394626491968098654
872 19550943873586759907
873 19708339920928391137
874 19866820830082967822
875 20026392824688441119
876 20187062157808866908
877 20348835110245934966
878 20511717992429797803
879 20675717142718768548
880 20840838929302903149
881 21007089748491815367
882 21174476026631073080
883 21343004218378071645
884 21512680808631298118
885 21683512310794211140
886 21855505268717434085
887 22028666254950582458
888 22203001872697440023
889 22378518754055681629
890 22555223561985093602
891 22733122988535132715
892 22912223756826245136
893 23092532619265209218
894 23274056359539614559
895 23456801790820929056
896 23640775757772192609
897 23825985134738755875
898 24012436827769250444
899 24200137772793939465
900 24389094937659019066
901 24579315320292528048
902 24770805950752042649
903 24963573889378085206
904 25157626228855267275
905 25352970092353144217
906 25549612635600869046
907 25747561045015432567
908 25946822539789883204
909 26147404370008899406
910 26349313818750638099
911 26552558200189578716
912 26757144861712055765
913 26963081182006320959
914 27170374573191822816
915 27379032478896425973
916 27589062376399493550
917 27800471774696209884
918 28013268216654528845
919 28227459277066538802
920 28443052564819332863
921 28660055720933362069
922 28878476420747291018
923 29098322371943277827
924 29319601316745871352
925 29542321029934163674
926 29766489321054792647
927 29992114032420905176
928 30219203041339321545
929 30447764258096255003
930 30677805628198701876
931 30909335130346855457
932 31142360778689778594
933 31376890620784457160
934 31612932739865819393
935 31850495252792366670
936 32089586312330596531
937 32330214105087155793
938 32572386853807731806
939 32816112815295665359
940 33061400282725367340
941 33308257583547336230
942 33556693081816164987
943 33806715176081900308
944 34058332301732697149
945 34311552928872464311
946 34566385564678231688
947 34822838751264019085
948 35080921068052973846
949 35340641129627407220
950 35602007588115767733
951 35865029131028781738
952 36129714483661320423
953 36396072406914588621
954 36664111699712951090
955 36933841196812105947
956 37205269771230928352
957 37478406332045572402
958 37753259826836398127
959 38029839239467937936
960 38308153592550965297
961 38588211945208269331
962 38870023395551931356
963 39153597078434843449
964 39438942167943251466
965 39726067875133960928
966 40014983450542212969
967 40305698181904513094
968 40598221396681898907
969 40892562459768334857
970 41188730776029438470
971 41486735787996376359
972 41786586978420108052
973 42088293867950726142
974 42391866017707284707
975 42697313026942518604
976 43004644535628315813
977 43313870222105758511
978 43624999805686306608
979 43938043044287095333
980 44253009737047889534
981 44569909721951580172
982 44888752878456976925
983 45209549125104438050
984 45532308422164561103
985 45857040769228888325
986 46183756207874563290
987 46512464819240046003
988 46843176726705795528
989 47175902093454936714
990 47510651125170036887
991 47847434067578658120
992 48186261209166288281
993 48527142878706720523
994 48870089447991207044
995 49215111329343599441
996 49562218978365785714
997 49911422891437532920
998 50262733608478276049
999 50616161710431596350
1000 50971717822043422851