1 1
2 129
3 2188
4 16513
5 78126
6 282252
7 823544
8 2113665
9 4785157
10 10078254
11 19487172
12 36130444
13 62748518
14 106237176
15 170939688
16 270549121
17 410338674
18 617285253
19 893871740
20 1290094638
21 1801914272
22 2513845188
23 3404825448
24 4624699020
25 6103593751
26 8094558822
27 10465138360
28 13599182072
29 17249876310
30 22051219752
31 27512614112
32 34630287489
33 42637932336
34 52933688946
35 64340198544
36 79017297541
37 94931877134
38 115309454460
39 137293757384
40 165132191790
41 194754273882
42 232446941088
43 271818611108
44 321791671236
45 373845175782
46 439222482792
47 506623120464
48 591961476748
49 678223896393
50 787363593879
51 897821018712
52 1036166277734
53 1174711139838
54 1350002848440
55 1522454799672
56 1740696128760
57 1955791367120
58 2225234043990
59 2488651484820
60 2822727067944
61 3142742836022
62 3549127220448
63 3940787336408
64 4432676798593
65 4902290717268
66 5500293271344
67 6060711605324
68 6775922523762
69 7449758080224
70 8299885612176
71 9095120158392
72 10114218870405
73 11047398519098
74 12246212150286
75 13354663127188
76 14760504042620
77 16048543577568
78 17710894702536
79 19203908986160
80 21136920627246
81 22887257593321
82 25123301330778
83 27136050989628
84 29755010373536
85 32058119244924
86 35064600832932
87 37742729366280
88 41189353405380
89 44231334895530
90 48226027675878
91 51676165507792
92 56223882622824
93 60197599677056
94 65354382539856
95 69834623559240
96 75771069025932
97 80798284478114
98 87490882634697
99 93249177506004
100 100788643610263
101 107213535210702
102 115818911413848
103 122987386542488
104 132629346298470
105 140776354414272
106 151537737039102
107 160578147647844
108 172810829738680
109 182803912081670
110 196396669157688
111 207710947169192
112 222809105304824
113 235260548044818
114 252297086358480
115 266005392950448
116 284847207507030
117 300261510147326
118 321036041541780
119 337931952940656
120 361309235636520
121 379749853070413
122 405413825846838
123 426122351253816
124 454315796831456
125 476843261796876
126 508361566396632
127 532875860165504
128 567382630219905
129 594739121104304
130 632395502527572
131 662062621900812
132 704080176664368
133 736142708246560
134 781831797086796
135 817599399513360
136 867318493380210
137 905824306333434
138 961018792348896
139 1002544368429380
140 1062449698557072
141 1108491387575232
142 1173270500432568
143 1222791163011096
144 1294620020196997
145 1347663836595060
146 1425114408963642
147 1483953885307884
148 1567610087113742
149 1630436461403550
150 1722751543407252
151 1789940649848552
152 1889345411327100
153 1963534978261818
154 2070262121506272
155 2149450490114112
156 2267131815681992
157 2351243277537494
158 2477304259214640
159 2570267973965544
160 2705525840365614
161 2804023568747712
162 2952456229538409
163 3057125241215468
164 3215977324613466
165 3331131101682336
166 3500550577662012
167 3622557586593624
168 3808643129726880
169 3937376448447807
170 4135497382595196
171 4277316613763180
172 4488540725226404
173 4637914326451398
174 4868812088250120
175 5026578012073544
176 5272237255375812
177 5445169448786160
178 5705842201523370
179 5888046306640860
180 6173305387688166
181 6364290927201662
182 6666225350505168
183 6876321325216136
184 7196660380546920
185 7416647832970884
186 7765490358340224
187 7996340318489928
188 8365867588222032
189 8618501905547840
190 9008666439141960
191 9273284218074432
192 9698696835321484
193 9974730326005058
194 10422978697676706
195 10726212089382384
196 11199511201137609
197 11514990476898414
198 12029143898274516
199 12358664279161400
200 12900952485707415
201 13260836992448912
202 13830546042180558
203 14206032135842640
204 14825718481991256
205 15215372401305132
206 15865372863980952
207 16292624326275336
208 16976556388952678
209 17419032343319280
210 18160149719441088
211 18619893262512572
212 19398005052144894
213 19900122906561696
214 20714581046571876
215 21236100811423608
216 22119796671689400
217 22657848276252928
218 23581704658535430
219 24171707959786424
220 25140296106983736
221 25748143671585132
222 26794712184825768
223 27424204663190048
224 28519565479841016
225 29206654362753907
226 30348610697781522
227 31058537410917804
228 32295982845252560
229 33025422047685710
230 34314695690607792
231 35114213347718784
232 36460459810776150
233 37281334283719578
234 38733734809005054
235 39580437909370464
236 41095101968832660
237 42018152861718080
238 43593221929344624
239 44543599279432080
240 46247582332414248
241 47219273189051282
242 48987731046083277
243 50054432356593028
244 51896112451231286
245 52986920129599518
246 54969783311742264
247 56089126967081320
248 58152449507040480
249 59373679565306064
250 61512780771797004
251 62764785704439252
252 65074221286105304
253 66350419135153056
254 68740985961350016
255 70143164907893712
256 72624976668147841
257 74051159531521794
258 76721346622455216
259 78180577822442896
260 80951526614246484
261 82543366373930670
262 85406078225204748
263 87034259659851768
264 90122305250971440
265 91775482510983588
266 94962409363806240
267 96778160751419640
268 100080530738715212
269 101921535994725990
270 105470322537223440
271 107345794852487792
272 111016767563005554
273 113067450131048896
274 116851335517012986
275 118941781243862172
276 123017855178738912
277 125129118027271454
278 129328223527390020
279 131652178006335584
280 135993625755503760
281 138338874920368362
282 142995388997204928
283 145380128593826228
284 150187719175527096
285 152798156347617120
286 157740060028431384
287 160388713729877808
288 165711362590000773
289 168377826969739603
290 173848634920762740
291 176786646438113432
292 182425691745865274
293 185384466926009358
294 191430051204717036
295 194428385903047320
296 200654186082436110
297 203935951225117920
298 210326303521057950
299 213647750910686064
300 220525552219255444
301 223854586266326752
302 230902343830463208
303 234583215041015976
304 241836213543740540
305 245529926807054772
306 253296012195774522
307 257021011458116444
308 265009600096380384
309 269096401754963744
310 277279113224720448
311 281399112371155272
312 290193009701052360
313 294313621587817418
314 303310382802336726
315 307877951444211408
316 317114149088460080
317 321673167473963574
318 331564568641555176
319 336151306631695320
320 346307307566876718
321 351344987053482672
322 361719040368454848
323 366790144517672760
324 377937284638509673
325 382991462349311018
326 394369156116795372
327 399974959634693960
328 411645292304797530
329 417226431119404416
330 429715912117021344
331 435307306210734212
332 448097609991727164
333 454263936390900038
334 467309928670577496
335 473499154877542824
336 487506322406954912
337 493638820681066034
338 507921561849767103
339 514750079122061784
340 529375723091430012
341 536143043370171264
342 551773843175450220
343 558546542307180400
344 574533484647590820
345 582019799775580224
346 598290948112230342
347 605767994083541364
348 623245690025381640
349 630634881591804950
350 648428563557487176
351 656671922754950480
352 674846368707591108
353 683003513396280738
354 702426858893414640
355 710565357494533392
356 730392033129886890
357 739395113034155328
358 759557973556670940
359 768530557342240920
360 790183463469261030
361 799006686676755861
362 820993529609014398
363 830892678518063644
364 853328521030169296
365 863089056703050348
366 887045450952881544
367 896731549611390224
368 921172532114831208
369 931929776946369474
370 956747570453244036
371 967426310946745872
372 994042963467225728
373 1004527481829495998
374 1031527901085200712
375 1043333056811564688
376 1070831557915540560
377 1082404174135808580
378 1111786745815671360
379 1123244937204690260
380 1153179138833730120
381 1165932382042122752
382 1196253664131601728
383 1208902895495334528
384 1241433194921152140
385 1253808515541077568
386 1286740212054652482
387 1300694729673723956
388 1334222071587096482
389 1347867523649523630
390 1383681359530327536
391 1397131559533775952
392 1433538111969510345
393 1448593016718976656
394 1485433771519895406
395 1500324593452736160
396 1539823668156644052
397 1554295348625559014
398 1594267692011820600
399 1610680245643473280
400 1651321924274142871
401 1667287938243362802
402 1710647972025909648
403 1726375761833886016
404 1770417106934322126
405 1788089886735796446
406 1832578145523700560
407 1849953817993125048
408 1897692863515899480
409 1914534320537457770
410 1962783039768362028
411 1981943582257553592
412 2030890713976104344
413 2049513998414602080
414 2101748538089518344
415 2120031119615677128
416 2172999217848691302
417 2193567078123483440
418 2247055172288187120
419 2267243475354978540
420 2324639940442873536
421 2344092097965587342
422 2401966230864121788
423 2424271171250152848
424 2482945821385686270
425 2504540566420026174
426 2567115854946458784
427 2588187006148901968
428 2651626952108847972
429 2675467064668278048
430 2739457004673645432
431 2762745569510280912
432 2831333984441381560
433 2853745728689236178
434 2922862427636627712
435 2948688474469991280
436 3018641000204616710
437 3043477247600039520
438 3118150326812448696
439 3142328914862177480
440 3217959424148717880
441 3245407825392238701
442 3321510533634482028
443 3348313266243628308
444 3429930870604867496
445 3455617270048176780
446 3537722401551516192
447 3567394977550967400
448 3650504381420473592
449 3678954248903875650
450 3767658412795254003
451 3795210032873641704
452 3884857429864079634
453 3916390141868631776
454 4006551326008396716
455 4037252106461757792
456 4133887759983694800
457 4163067000501310394
458 4260279444151456590
459 4294250997868934640
460 4392547053790747824
461 4424930743202406822
462 4529733521855723136
463 4561072096211304368
464 4666938873029223510
465 4702997672369677056
466 4809292122599825562
467 4844156483581198524
468 4958218317062794238
469 4991262678294948256
470 5105876490308789856
471 5144520291252036872
472 5260175540662065300
473 5296976027462706576
474 5420341719161632320
475 5455829966459496740
476 5580270338909052528
477 5621177233773784566
478 5746124307046738320
479 5785602523725084960
480 5919690538719963432
481 5956834601116587412
482 6091286241387615378
483 6135203568419993856
484 6270809323751729869
485 6312446773137134364
486 6457021774000500612
487 6496848334417832984
488 6642705536500440630
489 6688990027779443984
490 6835312696718337822
491 6879714958723010532
492 7036558386254263608
493 7078291371709412940
494 7235497378753490280
495 7285185241834068504
496 7443513564413795552
497 7490231635722781248
498 7659204663924482256
499 7703779066869753500
500 7874112782051813388
501 7926155999466849312
502 8096657355872663508
503 8146590668153303688
504 8329504265408815320
505 8376164651871304452
506 8559204068434744224
507 8614979669203801716
508 8799379078912967552
509 8851654953747076470
510 9048468273118288848
511 9098018766012043312
512 9295997013522923649
513 9354491435193946400
514 9552599579566311426
515 9608512561018417488
516 9820927106795371952
517 9872651887658687808
518 10085294539095133584
519 10147756546275658824
520 10361800308914267220
521 10419912285387762042
522 10648094262237056430
523 10703155179206186948
524 10932640075448108556
525 10998152690416914272
526 11227419496120878072
527 11289489592991767488
528 11535655114762276656
529 11592836327943575257
530 11839037243916882852
531 11908588073146816740
532 12155924541275445280
533 12220542060261606876
534 12484382736933133560
535 12545328363135460344
536 12810313995267152460
537 12883045318930201680
538 13147878143319652710
539 13216665723520570596
540 13501018884164113680
541 13563783707049367382
542 13847607535970925168
543 13925068548717236456
544 14210146248475049586
545 14281738435292550420
546 14585701066905307584
547 14652484962038521964
548 14957876770483995642
549 15038517880990525454
550 15343489780458220188
551 15419176952004479400
552 15746292912636660960
553 15815264022098151040
554 16141656225518017566
555 16227625458540294192
556 16555015155874351940
557 16633604317637114694
558 16983130962817290336
559 17056215011845337944
560 17407184161044679824
561 17495992616855962464
562 17845714864727518698
563 17929111329964120668
564 18304518283029806016
565 18379965576549451068
566 18754036588603583412
567 18848663667433949624
568 19224037149587626680
569 19310159666381286090
570 19710962168842608480
571 19790317317081631892
572 20191950474802228248
573 20289945869146857216
574 20690144071154237232
575 20781671327658575448
576 21211054411524884101
577 21292697885552828354
578 21720739679096408787
579 21824709953299066904
580 22253972933694225780
581 22347731976202201632
582 22805477390516632728
583 22891798032339158136
584 23350499590869274170
585 23458230741769991076
586 23914596233455207182
587 24014121782394769284
588 24504530508089088492
589 24592748248241994880
590 25081261781493104280
591 25194799163453729832
592 25683735913483699214
593 25785933216992382258
594 26307737708040211680
595 26401271755441690656
596 26923397287156821150
597 27040757442805143200
598 27560559867478502256
599 27668636431552444200
600 28227284038727824020
601 28321829503567564202
602 28877241628356151008
603 29001456563197375868
604 29557289950949139176
605 29668337020979086038
606 30261234740291060904
607 30361333167115869344
608 30955035334492660860
609 31082798313223696320
610 31673360558110065588
611 31789849993651472352
612 32423853096037400634
613 32525450580470426318
614 33155710478097021276
615 33291234814055628816
616 33921244860880266720
617 34040517062667048474
618 34713435826390322976
619 34820463128555011940
620 35493875943254331456
621 35631969404968985280
622 36300485495879030088
623 36426450465204358320
624 37144705379028459464
625 37253379827880937501
626 37966457184828446922
627 38112842767182584640
628 38826080241976638422
629 38954220583496480316
630 39716255736303271632
631 39829560546169634312
632 40590630287231876400
633 40740326458377507536
634 41495838604141301046
635 41631459451290165504
636 42442835054093028072
637 42557544370846295574
638 43363518555488696280
639 43521577891770587544
640 44327335368560298030
641 44463762187231646082
642 45323503329899264688
643 45444027132932496908
644 46302841190730968256
645 46464588575394854304
646 47315928642779786040
647 47460243783940422264
648 48375995320986831465
649 48496779532742729040
650 49405898643061121322
651 49575372028441406464
652 50482309108191023084
653 50628174571314961638
654 51596769792875520840
655 51724304398622838312
656 52690597609768357722
657 52863536355451428386
658 53822209614403169664
659 53975652627753217020
660 55006967882080414368
661 55132821210310712222
662 56154642501184713348
663 56336938353428268816
664 57356521214992066620
665 57511885224470746560
666 58600047794426104902
667 58732817835140336880
668 59819293427420513112
669 60004159803059825024
670 61081390979203024296
671 61243170197328509784
672 62400809269892143008
673 62532450726352012898
674 63679407867857518386
675 63874953097446388360
676 65017897293218636991
677 65180949228706560654
678 66402760206745970136
679 66540942392243916016
680 67760124613822286460
681 67956079855088155152
682 69162452594752093056
683 69333787611640219428
684 70631329243071391340
685 70768429756605864684
686 72052503957626271600
687 72259623440336333480
688 73540286306710236068
689 73711383102925260084
690 75080554171049848896
691 75222252078290067932
692 76585879272691935174
693 76794800640004558176
694 78144071236776835956
695 78324781327913741880
696 79775486065978216200
697 79915210500572712468
698 81351899725342838550
699 81571559412778436664
700 83003882713370432072
701 83181380885515294902
702 84710678035388611920
703 84856922195234793160
704 86380335194591148996
705 86601998145702575232
706 88107453228120215202
707 88295063641562367888
708 89916083107805860080
709 90058279596528053870
710 91662931116794807568
711 91893719512486427120
712 93490224471960417450
713 93675648669541522176
714 95381969581406037312
715 95531782401404886096
716 97229308661560521180
717 97461395223397391040
718 99140441897149078680
719 99334985490582398640
720 101143483697910587622
721 101285524262746737472
722 103071862581301506069
723 103315769737644205016
724 105093536080881044606
725 105286237251238938810
726 107185155528830210076
727 107334880228778779304
728 109226102368027177680
729 109469043563868952237
730 111338488314693494892
731 111537688450578390792
732 113548694043294053768
733 113691454465110461078
734 115678369899869338896
735 115935381243563745384
736 117910084114103220072
737 118106129495344903728
738 120218941226081662146
739 120368006731788145580
740 122471105665848207492
741 122723009803973928160
742 124797994112130217488
743 125003362773881021208
744 127237559521404570240
745 127379478983613747300
746 129584045156004983742
747 129850264345375351596
748 132043567679224181064
749 132243170026496039136
750 134589964328691844752
751 134734730815558692752
752 137066439919812312144
753 137329351121313083376
754 139630138463519306820
755 139840903210067973552
756 142317321966311481920
757 142452854616260543294
758 144898596899405043540
759 145174717067714886528
760 147606999605341014600
761 147806181513219494922
762 150405277283433835008
763 150547064971386838480
764 153129742293063095616
765 153403133711682793068
766 155948473518898154112
767 156159192490954496760
768 158903448949907476108
769 159031947967038559490
770 161741298504799006272
771 162023937054969685272
772 164712721873321522754
773 164913594364504305198
774 167789620127910390324
775 167925819567677614112
776 170780505961432827810
777 171059104275505056448
778 173874910550788548270
779 174085341667339894680
780 177121940231971306992
781 177238170887252147424
782 180229971179857097808
783 180522342277036251600
784 183492879010321220553
785 183693232300894256244
786 186868499156747988624
787 186992042977909461884
788 190147037745023510382
789 190430960135755668384
790 193541872555402964640
791 193747412779021594992
792 197097522773227944660
793 197202455415497515396
794 200504099972697112806
795 200804755734032090544
796 204078623241792198200
797 204271721896258160214
798 207777751688008053120
799 207887059468940024736
800 211369206313193881239
801 211653881794689648210
802 215080144033393801458
803 215282555094208010856
804 218976201256308883856
805 219067145331983747712
806 222702473276571296064
807 223004320756460466120
808 226613496901128442830
809 226798224993719412570
810 230663595388917741534
811 230752268637185668772
812 234584208659169514320
813 234872599137243288896
814 238644042521113131192
815 238840966595199652968
816 242904687427856152152
817 242970974875491287920
818 246974927349332052330
819 247278565112769443344
820 251251444462751644716
821 251421318647928806142
822 255670722111224413368
823 255740109319575723848
824 259954134376327898520
825 260244617361570432336
826 264387305795483668320
827 264568763060045171604
828 269040105499784623368
829 269080182677623033910
830 273484014430422349512
831 273782510243669941352
832 278143899884695235174
833 278301494321017002882
834 282970153077929363760
835 283015934010213468624
836 287640481085231270640
837 287923313327368536320
838 292474408320792231660
839 292640025382150628280
840 297554053153042226880
841 297558232693049339791
842 302387880637560767118
843 302685458325765976056
844 307470297443870101436
845 307611472411433369682
846 312730981091269717392
847 312740712997020203672
848 317817066312078982398
849 318091721363291786864
850 323085733068183376446
851 323226471092252506032
852 328610729556053286048
853 328581583454079382238
854 333876123793208353872
855 334169637766862200680
856 339408410448080188260
857 339520305862168167594
858 345135251342207868192
859 345105711415338434420
860 350671732699038038904
861 350930505640972643904
862 356394178466826237648
863 356513163590850929568
864 362410750018961978040
865 362341694668341920148
866 368133199000911466962
867 368410685409790251364
868 374149048585764600064
869 374229877485645539520
870 380380813206628875120
871 380300671259481909832
872 386386230830103020550
873 386632476558438553898
874 392608564940405098080
875 392701407193246448544
876 399147413539953219512
877 399022287095641845254
878 405360430017220894920
879 405621213634108475304
880 411898807813490688312
881 411937528360866188562
882 418657609475598792429
883 418528392172703776028
884 425179096448885284716
885 425409308355867536160
886 431932411345428051732
887 431981689649067218184
888 439031359148370208680
889 438846717384139826176
890 445774627836214804620
891 446007925329352378212
892 452855891603257262624
893 452856090213385287360
894 460193952104074794600
895 460009505752623828360
896 467264560821821443320
897 467461278992581108032
898 474585098108599958850
899 474589190396760486720
900 482289483492155266291
901 482029411454153494812
902 489582094240699779816
903 489793834750722933376
904 497261986283150237970
905 497216592978557045412
906 505214328301053499104
907 504953061238644082244
908 512869628266485697452
909 513033598508237150214
910 520805521733566755168
911 520749232824272831472
912 529137635233704301520
913 528804893035651052016
914 537035643064669040826
915 537219479853835841136
916 545348794273434129230
917 545237699890682317728
918 553958378725092568560
919 553615931892541912040
920 562246288890608671920
921 562361973070358779472
922 570816065873110480038
923 570705310971023263056
924 579841005010880280192
925 579425612045782189634
926 588378300411258263472
927 588513953625492250616
928 597368175764990485590
929 597186522625496288610
930 606686699735688340224
931 606245174378390633820
932 615626673027061391514
933 615701257868087735136
934 624896186381974609596
935 624722083722344114928
936 634652244845547809790
937 634128301193131823834
938 643872885500048325024
939 643958204034144510584
940 653591771197434472032
941 653322121999805002182
942 663643117571512756488
943 663104307820195349136
944 673302471693395843220
945 673329079872830547840
946 683309907542689148304
947 683045843705463763164
948 693845758205550655040
949 693207884828794196764
950 703802065673275079460
951 703820890433032299912
952 714274941312311664240
953 713921242537737182538
954 725131863156818209014
955 724484602821283074432
956 735548454901261937040
957 735499058910149360160
958 746342725560535959840
959 745986172535061570096
960 757720388956326258984
961 756943935248308934433
962 768431663544039776148
963 768391647264114251508
964 779731858170803819666
965 779285781449471161308
966 791441260326179207424
967 790651899389404340024
968 802663973190074493645
969 802536836204667998880
970 814305633734690332956
971 813831713247384370692
972 826548841504420671364
973 825639399353805322720
974 838093435139900454936
975 837985319620292507384
976 850266311814799236662
977 849692815304643397554
978 862879713583548273936
979 861943630898795141160
980 874973012100076840734
981 874745419524987772190
982 887483229675268358628
983 886899938586555644328
984 900679899562896995640
985 899620145998165492164
986 913099586950514269260
987 912891431289256862208
988 926199753607413837160
989 925494924340533876384
990 939788896196594837016
991 938675713398686304032
992 952769736272478444768
993 952452385989086455856
994 966239881008238780992
995 965533005473763536400
996 980437570661899034832
997 979188057829902100814
998 993787499626198201500
999 993475228981830260240
1000 1007886912945893910540