0 1
1 3370
2 108108
3 957332
4 4721127
5 16627422
6 47043624
7 114106128
8 246902225
9 489197948
10 903720482
11 1576984058
12 2624673317
13 4197566692
14 6488021194
15 9736993054
16 14241624013
17 20363359008
18 28536634496
19 39278092476
20 53196371385
21 71002416300
22 93520372350
23 121698990952
24 156623626331
25 199528736950
26 251810985748
27 315042836672
28 390986758437
29 481609916084
30 589099478932
31 715878406176
32 864621859705
33 1038274083726
34 1240065922112
35 1473532792046
36 1742533306633
37 2051268341440
38 2404300763124
39 2806575588916
40 3263440820789
41 3780668697952
42 4364477637364
43 5021554577974
44 5759078028395
45 6584741503016
46 7506777676222
47 8533982910508
48 9675742518121
49 10942056379772
50 12343565314592
51 13891577789632
52 15598097397373
53 17475850656222
54 19538315596522
55 21799750650500
56 24275224347733
57 26980645294810
58 29932792979362
59 33149348839708
60 36648928178465
61 40451112320496
62 44576481637128
63 49046648792734
64 53884292878519
65 59113193748084
66 64758267261868
67 70845600709866
68 77402489167825
69 84457472007518
70 92040370363522
71 100182324731460
72 108915833546513
73 118274791867670
74 128294531069142
75 139011858611092
76 150465098842633
77 162694133859522
78 175740445419972
79 189647156887202
80 204459076259301
81 220222739197178
82 236986453167022
83 254800341554206
84 273716388919635
85 293788486197364
86 315072477066144
87 337626204231362
88 361509556910189
89 386784518198466
90 413515213670824
91 441767959830130
92 471611313823953
93 503116122977256
94 536355575623472
95 571405251721136
96 608343174801005
97 647249863664106
98 688208385446352
99 731304408398754
100 776626256067657
101 824264961157882
102 874314320830088
103 926870951644180
104 982034345975311
105 1039906928038382
106 1100594111420670
107 1164204356188250
108 1230849227536825
109 1300643453977266
110 1373704987106236
111 1450155060871738
112 1530118252461373
113 1613722542648804
114 1701099377801294
115 1792383731304142
116 1887714166689157
117 1987232900138028
118 2091085864729442
119 2199422774022358
120 2312397187423485
121 2430166574847378
122 2552892383206004
123 2680740102146692
124 2813879331661347
125 2952483848903302
126 3096731676917968
127 3246805152535360
128 3402890996223981
129 3565180381060124
130 3733869003702418
131 3909157154439018
132 4091249789284665
133 4280356601102404
134 4476692092825026
135 4680475649652486
136 4891931613395009
137 5111289355747392
138 5338783353755704
139 5574653264164964
140 5819144000011373
141 6072505806044612
142 6334994336442750
143 6606870731310416
144 6888401695518375
145 7179859576273934
146 7481522443087196
147 7793674166415008
148 8116604498750897
149 8450609154343884
150 8795989891414172
151 9153054592943040
152 9522117350016357
153 9903498543686942
154 10297524929442768
155 10704529720143182
156 11124852671613933
157 11558840166653328
158 12006845301756236
159 12469227972191628
160 12946354959852281
161 13438600019405168
162 13946343967269068
163 14469974768833742
164 15009887628567663
165 15566485078307504
166 16140177068492574
167 16731381057526148
168 17340522104138885
169 17968032957817796
170 18614354152300936
171 19279934097075600
172 19965229172000729
173 20670703819875942
174 21396830642194002
175 22144090492776340
176 22912972574657937
177 23703974534791002
178 24517602562058578
179 25354371483048044
180 26214804861195861
181 27099435093626416
182 28008803511430336
183 28943460477570406
184 29903965488289611
185 30890887272085876
186 31904803892252324
187 32946302846916210
188 34015981172713893
189 35114445545895766
190 36242312387131970
191 37400207963685132
192 38588768495349373
193 39808640257686094
194 41060479689098846
195 42344953495134036
196 43662738756687541
197 45014523035372218
198 46401004482858892
199 47822891947305762
200 49280905083836401
201 50775774462033002
202 52308241677547134
203 53879059460658782
204 55488991789022551
205 57138813997287460
206 58829312890981304
207 60561286857193210
208 62335545979591761
209 64152912150172338
210 66014219185411776
211 67920312939075306
212 69872051419510517
213 71870304903515984
214 73915956054770000
215 76009900038762984
216 78153044642363817
217 80346310389810706
218 82590630663417976
219 84886951820627538
220 87236233315851461
221 89639447818586210
222 92097581336393904
223 94611633334073860
224 97182616857785451
225 99811558655279182
226 102499499301156334
227 105247493318161802
228 108056609303583501
229 110927930051601362
230 113862552680829492
231 116861588757723618
232 119926164425261041
233 123057420527408836
234 126256512738944646
235 129524611690979894
236 132862903101924473
237 136272587904067332
238 139754882375679970
239 143311018268656766
240 146942242941760393
241 150649819489316010
242 154435026875601724
243 158299160064599076
244 162243530155523311
245 166269464513632606
246 170378306906901336
247 174571417637882016
248 178850173681524761
249 183215968818094444
250 187670213772130978
251 192214336346424202
252 196849781562118237
253 201578011793737940
254 206400506910440602
255 211318764412096542
256 216334299571682629
257 221448645572419600
258 226663353651310736
259 231979993237329596
260 237400152096107185
261 242925436469172748
262 248557471219783774
263 254297899973222504
264 260148385263772163
265 266110608676062742
266 272186270993196868
267 278377092339147568
268 284684812328027981
269 291111190207543828
270 297658005009410436
271 304327055693853328
272 311120161301176033
273 318039161097311582
274 325085914726535168
275 332262302358069342
276 339570224839945057
277 347011603846653840
278 354588382034160772
279 362302523188606484
280 370156012382465997
281 378150856124303408
282 386289082516080196
283 394572741403955734
284 403003904536748675
285 411584665717786216
286 420317140964512350
287 429203468661388812
288 438245809720653873
289 447446347736267964
290 456807289145826704
291 466330863385554192
292 476019323053363909
293 485874944064902686
294 495900025817763226
295 506096891348571604
296 516467887498355165
297 527015385070676618
298 537741778998150818
299 548649488501628524
300 559740957257865881
301 571018653559750560
302 582485070485127768
303 594142726058071902
304 605994163418862447
305 618041950986304292
306 630288682628857404
307 642736977827998378
308 655389481850507785
309 668248865912876158
310 681317827354742242
311 694599089804346628
312 708095403353124857
313 721809544722201142
314 735744317438140294
315 749902552000484804
316 764287106058658673
317 778900864580551138
318 793746740030576436
319 808827672539296466
320 824146630082640525
321 839706608652570250
322 855510632437452270
323 871561753993768782
324 887863054427647211
325 904417643567608580
326 921228660147258288
327 938299271979075682
328 955632676138258757
329 973232099137558354
330 991100797112280952
331 1009242055996159506
332 1027659191707518505
333 1046355550326184936
334 1065334508280808272
335 1084599472526815056
336 1104153880734888053
337 1124001201469956330
338 1144144934380837824
339 1164588610380268466
340 1185335791835700689
341 1206390072750375162
342 1227755078955279544
343 1249434468291254564
344 1271431930802117335
345 1293751188917805406
346 1316395997648657022
347 1339370144769596778
348 1362677451015577201
349 1386321770266797602
350 1410306989745311372
351 1434637030201281722
352 1459315846110746933
353 1484347425862916692
354 1509735791959099742
355 1535485001201032270
356 1561599144890972413
357 1588082349021064460
358 1614938774474592322
359 1642172617216383318
360 1669788108495225125
361 1697789515035300466
362 1726181139239772068
363 1754967319383252084
364 1784152429816547019
365 1813740881160165734
366 1843737120510228928
367 1874145631633006896
368 1904970935171998165
369 1936217588843500908
370 1967890187644852562
371 1999993364051038810
372 2032531788224098833
373 2065510168210762900
374 2098933250153027922
375 2132805818486827622
376 2167132696153770073
377 2201918744800844432
378 2237168864993325192
379 2272887996415506372
380 2309081118084777221
381 2345753248553387908
382 2382909446123688222
383 2420554809050928816
384 2458694475759667695
385 2497333625047597774
386 2536477476303125964
387 2576131289710231152
388 2616300366467207289
389 2656990048992555916
390 2698205721144898124
391 2739952808429892240
392 2782236778221319533
393 2825063139969031246
394 2868437445421199312
395 2912365288833296926
396 2956852307191519205
397 3001904180422787776
398 3047526631619346332
399 3093725427249793484
400 3140506377384844337
401 3187875335909395872
402 3235838200749459548
403 3284400914085249550
404 3333569462579291431
405 3383349877590537552
406 3433748235403642750
407 3484770657444111300
408 3536423310508744685
409 3588712406981810276
410 3641644205066666296
411 3695225009002956608
412 3749461169299403713
413 3804359082952034054
414 3859925193678144194
415 3916165992135546692
416 3973088016157714617
417 4030697850974052458
418 4089002129446209682
419 4148007532289381148
420 4207720788309794925
421 4268148674627032128
422 4329298016912694224
423 4391175689613746822
424 4453788616192357027
425 4517143769350265732
426 4581248171269800308
427 4646108893839265170
428 4711733058895135101
429 4778127838448468694
430 4845300454928272738
431 4913258181408943148
432 4982008341854805765
433 5051558311348574414
434 5121915516337073486
435 5193087434860717796
436 5265081596800407229
437 5337905584108033082
438 5411567031054550204
439 5486073624461499314
440 5561433103950262073
441 5637653262174604122
442 5714741945071103230
443 5792707052092717806
444 5871556536460393615
445 5951298405397647124
446 6031940720383356296
447 6113491597387363578
448 6195959207124440777
449 6279351775290916514
450 6363677582819820752
451 6448944966118525930
452 6535162317325076717
453 6622338084546849712
454 6710480772118058288
455 6799598940839435752
456 6889701208236920913
457 6980796248802353778
458 7072892794253347496
459 7165999633775001538
460 7260125614280949741
461 7355279640656095938
462 7451470676018843808
463 7548707741964843892
464 7646999918830410963
465 7746356345937287454
466 7846786221857237934
467 7948298804657833978
468 8050903412168231525
469 8154609422225965986
470 8259426272943918276
471 8365363462958125250
472 8472430551695923849
473 8580637159624781972
474 8689992968521626582
475 8800507721722683670
476 8912191224393996177
477 9025053343782278212
478 9139104009486612098
479 9254353213710322014
480 9370811011533856081
481 9488487521167667946
482 9607392924226289836
483 9727537465982227316
484 9848931455641212471
485 9971585266597117086
486 10095509336708391944
487 10220714168553986800
488 10347210329710981793
489 10475008453011519516
490 10604119236821617570
491 10734553445299118042
492 10866321908673687253
493 10999435523505770884
494 11133905252967786986
495 11269742127104092126
496 11406957243113356541
497 11545561765609546688
498 11685566926905488672
499 11826984027274855292
500 11969824435236923881
501 12114099587819573292
502 12259820990845224894
503 12407000219194854952
504 12555648917095124971
505 12705778798383397430
506 12857401646796061684
507 13010529316234558560
508 13165173731054890421
509 13321346886334660148
510 13479060848163771636
511 13638327753912470976
512 13799159812523243657
513 13961569304779863534
514 14125568583600475200
515 14291170074307656334
516 14458386274922691577
517 14627229756436635936
518 14797713163105786516
519 14969849212723752628
520 15143650696918113701
521 15319130481423501760
522 15496301506379451924
523 15675176786604484790
524 15855769411895155931
525 16038092547301143912
526 16222159433425486974
527 16407983386700682412
528 16595577799690116921
529 16784956141365164732
530 16976131957407818112
531 17169118870488790048
532 17363930580571332941
533 17560580865190351646
534 17759083579757416906
535 17959452657840876004
536 18161702111472067493
537 18365846031426435322
538 18571898587530932770
539 18779874028946145916
540 18989786684474893393
541 19201650962845346320
542 19415481353020830504
543 19631292424483948766
544 19849098827547573351
545 20068915293639976596
546 20290756635617020236
547 20514637748048281386
548 20740573607530445441
549 20968579272974433374
550 21198669885919985858
551 21430860670823797892
552 21665166935375300897
553 21901604070785791510
554 22140187552105418422
555 22380932938513311412
556 22623855873635760409
557 22868972085837350850
558 23116297388540341796
559 23365847680516794306
560 23617638946209155445
561 23871687256023385818
562 24128008766650736814
563 24386619721361883454
564 24647536450329901763
565 24910775370925393492
566 25176352988040670528
567 25444285894385877698
568 25714590770814371421
569 25987284386619846818
570 26262383599862917576
571 26539905357669233778
572 26819866696557269953
573 27102284742737439912
574 27387176712441080048
575 27674559912220567472
576 27964451739279505597
577 28256869681773831850
578 28551831319143212592
579 28849354322413146754
580 29149456454527557017
581 29452155570651895738
582 29757469618506939496
583 30065416638672883444
584 30376014764924346335
585 30689282224535459726
586 31005237338616070270
587 31323898522417830202
588 31645284285671604073
589 31969413232894546514
590 32296304063728720604
591 32625975573249169402
592 32958446652303732589
593 33293736287822118276
594 33631863563156925166
595 33972847658393700494
596 34316707850693174965
597 34663463514602313388
598 35013134122397748898
599 35365739244397832854
600 35721298549307275661
601 36079831804530181650
602 36441358876515903828
603 36805899731073070372
604 37173474433716639667
605 37544103149982925062
606 37917806145777857584
607 38294603787692994528
608 38674516543354997245
609 39057564981742630268
610 39443769773537440402
611 39833151691441753098
612 40225731610530560297
613 40621530508570499492
614 41020569466372957794
615 41422869668114040454
616 41828452401688877233
617 42237339059032587168
618 42649551136475794776
619 43065110235066576356
620 43484038060927193565
621 43906356425577028100
622 44332087246290518590
623 44761252546421090512
624 45193874455760303991
625 45629975210862764110
626 46069577155406487228
627 46512702740518798592
628 46959374525137902977
629 47409615176339776524
630 47863447469700949372
631 48320894289626376736
632 48781978629713441205
633 49246723593080810046
634 49715152392733642832
635 50187288351893441966
636 50663154904364473373
637 51142775594864595120
638 51626174079392898924
639 52113374125561523916
640 52604399612964504489
641 53099274533510576272
642 53598022991793238124
643 54100669205424535054
644 54607237505406342175
645 55117752336465131696
646 55632238257424464222
647 56150719941540746948
648 56673222176876940181
649 57199769866639291332
650 57730388029552264552
651 58265101800196257712
652 58803936429383740393
653 59346917284497961062
654 59894069849870301362
655 60445419727119957940
656 61000992635532520993
657 61560814412400638010
658 62124911013403801682
659 62693308512950002828
660 63266033104556735685
661 63843111101193624336
662 64424568935664653408
663 65010433160951775334
664 65600730450598351419
665 66195487599053747284
666 66794731522057992388
667 67398489256987347826
668 68006787963240192405
669 68619654922583570198
670 69237117539540288002
671 69859203341736450060
672 70485939980289775053
673 71117355230158102030
674 71753476990528935102
675 72394333285168928052
676 73039952262814641413
677 73690362197523013242
678 74345591489063336812
679 75005668663268701442
680 75670622372429199041
681 76340481395644342538
682 77015274639217485822
683 77695031137009227326
684 78379780050833051655
685 79069550670809702084
686 79764372415764052184
687 80464274833580454842
688 81169287601600828289
689 81879440526980989266
690 82594763547089961824
691 83315286729867278250
692 84041040274223519013
693 84772054510398589136
694 85508359900363473552
695 86249987038179496616
696 86996966650401301305
697 87749329596437075346
698 88507106868952762712
699 89270329594233264114
700 90039029032587864917
701 90813236578712417762
702 91592983762095995408
703 92378302247384038820
704 93169223834786243451
705 93965780460440680622
706 94768004196822901230
707 95575927253111038250
708 96389581975596136445
709 97209000848048219186
710 98034216492127852756
711 98865261667753185378
712 99702169273512729953
713 100544972347033383204
714 101393704065394435494
715 102248397745496553142
716 103109086844477023977
717 103975804960079710788
718 104848585831071516322
719 105727463337613315838
720 106612471501677650265
721 107503644487420620778
722 108401016601600818844
723 109304622293952190852
724 110214496157604188607
725 111130672929455612062
726 112053187490595989048
727 112982074866680378880
728 113917370228351990121
729 114859108891617953164
730 115807326318273159458
731 116762058116277011178
732 117723340040178490765
733 118691207991493870324
734 119665698019133020346
735 120646846319778087006
736 121634689238311023349
737 122629263268193242672
738 123630605051894381104
739 124638751381272909564
740 125653739198006136673
741 126675605593971787532
742 127704387811679230110
743 128740123244652029096
744 129782849437860404755
745 130832604088104744214
746 131889425044449301796
747 132953350308606676048
748 134024418035372734557
749 135102666533012065044
750 136188134263694133732
751 137280859843879692720
752 138380882044758180977
753 139488239792635096382
754 140602972169370622208
755 141725118412767972222
756 142854717917013251793
757 143991810233064758128
758 145136435069094085156
759 146288632290876387348
760 147448441922232711101
761 148615904145421230608
762 149791059301580814948
763 150973947891123217942
764 152164610574177890163
765 153363088170985131304
766 154569421662342129694
767 155783652189997085708
768 157005821057096488065
769 158235969728580190076
770 159474139831629932016
771 160720373156065378800
772 161974711654793870869
773 163237197444207431902
774 164507872804633757562
775 165786780180734174900
776 167073962181955878317
777 168369461582930849322
778 169673321323929322018
779 170985584511259671884
780 172306294417723120201
781 173635494483014573376
782 174973228314178575736
783 176319539686011108126
784 177674472541516771231
785 179038070992311552196
786 180410379319081247964
787 181791441971985181290
788 183181303571115873593
789 184580008906903719166
790 185987602940577889570
791 187404130804571974852
792 188829637802986129033
793 190264169411993659574
794 191707771280304423526
795 193160489229572374116
796 194622369254860189441
797 196093457525047785058
798 197573800383298184852
799 199063444347466980722
800 200562436110569455261
801 202070822541190997482
802 203588650683955459054
803 205115967759936535022
804 206652821167127363291
805 208199258480852851300
806 209755327454240528464
807 211321076018633827810
808 212896552284064172981
809 214481804539665223858
810 216076881254146207896
811 217681831076207110546
812 219296702835013260697
813 220921545540611474984
814 222556408384405878800
815 224201340739575013584
816 225856392161548903237
817 227521612388427105066
818 229197051341457031456
819 230882759125452953618
820 232578786029275559841
821 234285182526251921210
822 236001999274656296344
823 237729287118131039620
824 239467097086168662311
825 241215480394533692542
826 242974488445745974014
827 244744172829503486922
828 246524585323166894241
829 248315777892183304002
830 250117802690572073132
831 251930712061349520378
832 253754558537015968741
833 255589394839981418356
834 257435273883053837566
835 259292248769865776014
836 261160372795363914413
837 263039699446236627212
838 264930282401404771970
839 266832175532450210966
840 268745432904107850293
841 270670108774695100530
842 272606257596605175684
843 274553934016737502356
844 276513192876992259291
845 278484089214701744486
846 280466678263126165536
847 282461015451885944656
848 284467156407458770021
849 286485156953612848204
850 288515073111905197138
851 290556961102115855482
852 292610877342747427457
853 294676878451460228980
854 296755021245573094642
855 298845362742499470182
856 300947960160249462089
857 303062870917866886000
858 305190152635932569256
859 307329863137002334916
860 309482060446111567605
861 311646802791214142788
862 313824148603688236254
863 316014156518776208304
864 318216885376091667263
865 320432394220060288142
866 322660742300428140588
867 324901989072703451728
868 327156194198666178761
869 329423417546810725708
870 331703719192856771116
871 333997159420192918128
872 336303798720388787773
873 338623697793639612142
874 340956917549279573328
875 343303519106227349502
876 345663563793500710037
877 348037113150662993760
878 350424228928338970812
879 352824973088662262924
880 355239407805792451937
881 357667595466363451968
882 360109598670001875196
883 362565480229776335054
884 365035303172717079895
885 367519130740266237136
886 370017026388798694590
887 372529053790073295492
888 375055276831754978173
889 377595759617866900964
890 380150566469313850904
891 382719761924335308512
892 385303410739030105169
893 387901577887810437766
894 390514328563927785506
895 393141728179927853284
896 395783842368177758665
897 398440736981321914058
898 401112478092810463378
899 403799131997356113084
900 406500765211463829341
901 409217444473888596640
902 411949236746166386288
903 414696209213072852742
904 417458429283155552787
905 420235964589193589732
906 423028882988731094164
907 425837252564537794578
908 428661141625143770605
909 431500618705300960278
910 434355752566519164962
911 437226612197528503468
912 440113266814816679637
913 443015785863092361742
914 445934239015823723694
915 448868696175702760004
916 451819227475185079693
917 454785903276955167098
918 457768794174467439516
919 460767970992412432146
920 463783504787259130505
921 466815466847722089850
922 469863928695305021310
923 472928962084768856142
924 476010639004676596671
925 479109031677862303540
926 482224212561977222568
927 485356254349959705402
928 488505229970582591097
929 491671212588924070594
930 494854275606916334192
931 498054492663817357866
932 501271937636760827805
933 504506684641228859056
934 507758808031603175792
935 511028382401638772776
936 514315482585016362593
937 517620183655816957810
938 520942560929075596424
939 524282689961256855266
940 527640646550809832189
941 531016506738644601282
942 534410346808688463104
943 537822243288363319444
944 541252272949143202915
945 544700512807032581886
946 548167040123125147822
947 551651932404083061018
948 555155267402697007061
949 558677123118366360962
950 562217577797660524132
951 565776709934800017602
952 569354598272219077753
953 572951321801047689332
954 576566959761675451382
955 580201591644234527510
956 583855297189164793473
957 587528156387697715460
958 591220249482422757442
959 594931656967772198238
960 598662459590588810145
961 602412738350611592106
962 606182574501044731148
963 609972049549044262484
964 613781245256288291719
965 617610243639464592734
966 621459126970842102248
967 625327977778759432656
968 629216878848197650545
969 633125913221269715388
970 637055164197794519842
971 641004715335787265210
972 644974650452034775173
973 648965053622586785060
974 652976009183332540682
975 657007601730493012382
976 661059916121198756653
977 665133037473983065952
978 669227051169361104832
979 673342042850323972412
980 677478098422919124761
981 681635304056745361068
982 685813746185534509822
983 690013511507647349736
984 694234686986656571515
985 698477359851843610294
986 702741617598782894804
987 707027547989839602432
988 711335239054755173189
989 715664779091145998516
990 720016256665090211924
991 724389760611627288160
992 728785380035346122393
993 733203204310885550926
994 737643323083523696192
995 742105826269679420206
996 746590804057502947305
997 751098346907378226816
998 755628545552514845492
999 760181490999451310644
1000 764757274528648229397