0 1
1 1
2 4
3 16
4 58
5 190
6 564
7 1526
8 3794
9 8747
10 18869
11 38402
12 74273
13 137372
14 244271
15 419488
16 698415
17 1131045
18 1786650
19 2759580
20 4176372
21 6204378
22 9062142
23 13031778
24 18473624
25 25843471
26 35712691
27 48791614
28 65956531
29 88280728
30 117069985
31 153903004
32 200677261
33 259660809
34 333550592
35 425537864
36 539381342
37 679488758
38 851007512
39 1059925166
40 1313180558
41 1618786355
42 1985963905
43 2425291290
44 2948865525
45 3570479892
46 4305817443
47 5172661752
48 6191126043
49 7383901869
50 8776528566
51 10397684756
52 12279503224
53 14457910546
54 16972992898
55 19869389530
56 23196715444
57 27010014871
58 31370247199
59 36344807062
60 42008080359
61 48442038032
62 55736869493
63 63991657652
64 73315097561
65 83826260753
66 95655407420
67 108944848640
68 123849860930
69 140539655470
70 159198404412
71 180026326758
72 203240836362
73 229077754683
74 257792590989
75 289661892786
76 324984669321
77 364083891084
78 407308068311
79 455032911568
80 507663077575
81 565634003509
82 629413833106
83 699505437964
84 776448537532
85 860821921354
86 953245777222
87 1054384128978
88 1164947387792
89 1285695020831
90 1417438341323
91 1561043424110
92 1717434150875
93 1887595389320
94 2072576310665
95 2273493849932
96 2491536313573
97 2727967139097
98 2984128811448
99 3261446940984
100 3561434508006
101 3885696278886
102 4235933398944
103 4613948167326
104 5021648999238
105 5461055580995
106 5934304223449
107 6443653419466
108 6991489611229
109 7580333173252
110 8212844617099
111 8891831023912
112 9620252710963
113 10401230138557
114 11238051063726
115 12134177947268
116 13093255620800
117 14119119220610
118 15215802395210
119 16387545793610
120 17638805841452
121 18974263812263
122 20398835201207
123 21917679408838
124 23536209742479
125 25260103742976
126 27095313844701
127 29048078376804
128 31124932913841
129 33332721984033
130 35678611143540
131 38170099425264
132 40815032170826
133 43621614254494
134 46598423707972
135 49754425755094
136 53098987265602
137 56641891637323
138 60393354116197
139 64364037563746
140 68565068681713
141 73008054703740
142 77705100564095
143 82668826553600
144 87912386473055
145 93449486294597
146 99294403341578
147 105462005997692
148 111967773956228
149 118827819020474
150 126058906466446
151 133678476979266
152 141704669174664
153 150156342717231
154 159053102047203
155 168415320727710
156 178264166424579
157 188621626530936
158 199510534449009
159 210954596541692
160 222978419766589
161 235607540005417
162 248868451101808
163 262788634620712
164 277396590342766
165 292721867507158
166 308795096816680
167 325648023218830
168 343313539476990
169 361825720545875
170 381219858765617
171 401532499889018
172 422801479956677
173 445065963034868
174 468366479831219
175 492744967203416
176 518244808576331
177 544910875283149
178 572789568846246
179 601928864213748
180 632378353967880
181 664189293521394
182 697414647318546
183 732109136057274
184 768329284949412
185 806133473035959
186 845581983574607
187 886737055516918
188 929662936092727
189 974425934519536
190 1021094476854853
191 1069739162009620
192 1120432818941065
193 1173250565043505
194 1228269865755820
195 1285570595404512
196 1345235099301458
197 1407348257115662
198 1471997547538508
199 1539273114262214
200 1609267833291386
201 1682077381607771
202 1757800307208509
203 1836538100538386
204 1918395267336793
205 2003479402920300
206 2091901267921959
207 2183774865508656
208 2279217520098039
209 2378349957596757
210 2481296387181954
211 2588184584648172
212 2699145977342028
213 2814315730707242
214 2933832836462806
215 3057840202437298
216 3186484744082560
217 3319917477690175
218 3458293615334395
219 3601772661565390
220 3750518511876907
221 3904699552972648
222 4064488764855897
223 4230063824767148
224 4401607212994709
225 4579306320583481
226 4763353558967336
227 4953946471550744
228 5151287847265526
229 5355585836128838
230 5567054066828720
231 5785911766363774
232 6012383881763766
233 6246701203918179
234 6489100493539977
235 6739824609292074
236 6999122638104237
237 7267250027708388
238 7544468721420507
239 7831047295197576
240 8127261096998243
241 8433392388476125
242 8749730489034910
243 9076571922274660
244 9414220564858960
245 9762987797832802
246 10123192660421338
247 10495162006339882
248 10879230662645788
249 11275741591163079
250 11685046052510951
251 12107503772767526
252 12543483112800479
253 12993361240296416
254 13457524304521133
255 13936367613843140
256 14430295816053089
257 14939723081512001
258 15465073289161444
259 16006780215429072
260 16565287726063194
261 17141049970930302
262 17734531581809748
263 18346207873220022
264 18976565046311346
265 19626100395859563
266 20295322520396565
267 20984751535512770
268 21694919290367425
269 22426369587442780
270 23179658405578447
271 23955354126322528
272 24754037763636367
273 25576303196990053
274 26422757407886074
275 27294020719848796
276 28190727041917716
277 29113524115682714
278 30063073765899806
279 31040052154726178
280 32045150039613560
281 33079073034899279
282 34142541877134611
283 35236292694190334
284 36361077278179667
285 37517663362239064
286 38706834901207617
287 39929392356246108
288 41186152983437037
289 42477951126407241
290 43805638513015008
291 45170084556143880
292 46572176658645630
293 48012820522475190
294 49492940462060600
295 51013479721951342
296 52575400798788718
297 54179685767642227
298 55827336612756193
299 57519375562751194
300 59256845430325141
301 61040809956499156
302 62872354159453699
303 64752584688000696
304 66682630179737723
305 68663641623930605
306 70696792729171094
307 72783280295856596
308 74924324593539224
309 77121169743191762
310 79375084104438434
311 81687360667798682
312 84059317451992468
313 86492297906355927
314 88987671318416511
315 91546833226677078
316 94171205838658695
317 96862238454252240
318 99621407894429205
319 102450218935362420
320 105350204748007737
321 108322927343198033
322 111369978022301212
323 114492977833494208
324 117693578033705314
325 120973460556277486
326 124334338484405596
327 127777956530400934
328 131306091520836586
329 134920552887627643
330 138623183165100525
331 142415858493106034
332 146300489126231081
333 150279019949164364
334 154353430998271607
335 158525737989436304
336 162797992852222247
337 167172284270414453
338 171650738228995442
339 176235518567614156
340 180928827540605148
341 185732906383616010
342 190650035886901350
343 195682536975341970
344 200832771295248240
345 206103141808007007
346 211496093390631723
347 217014113443275822
348 222659732503769723
349 228435524869242184
350 234344109224887081
351 240388149279937036
352 246570354410905669
353 252893480312160601
354 259360329653889688
355 265973752747523320
356 272736648218675974
357 279651963687670566
358 286722696457709504
359 293951894210756702
360 301342655711195174
361 308898131517325187
362 316621524700768313
363 324516091573843082
364 332585142424978301
365 340832042262230468
366 349260211564972075
367 357873127043817960
368 366674322408857235
369 375667389146258685
370 384855977303317902
371 394243796282014788
372 403834615641150432
373 413632265907132738
374 423640639393480554
375 433863691029116426
376 444305439195518476
377 454969966572802279
378 465861420994803991
379 476984016313236358
380 488342033270989615
381 499939820384649664
382 511781794836306301
383 523872443374724644
384 536216323225953297
385 548818063013443169
386 561682363687751252
387 574813999465904048
388 588217818780495722
389 601898745238596446
390 615861778590546788
391 630111995708714390
392 644654551576289570
393 659494680286196875
394 674637696050200005
395 690088994218277922
396 705854052308350353
397 721938431046431292
398 738347775417289503
399 755087815725695424
400 772164368668334271
401 789583338416465541
402 807350717709409514
403 825472588958941756
404 843955125364677028
405 862804592040524410
406 882027347152295854
407 901629843066550786
408 921618627510759784
409 942000344744870767
410 962781736744361539
411 983969644394862942
412 1005571008698437283
413 1027592871991597112
414 1050042379175149841
415 1072926778955954108
416 1096253425100674205
417 1120029777701619305
418 1144263404454754640
419 1168961981949972200
420 1194133296973708942
421 1219785247824000918
422 1245925845638062152
423 1272563215732477518
424 1299705598956099294
425 1327361353055737491
426 1355538954054734481
427 1384246997644514874
428 1413494200589202021
429 1443289402143392948
430 1473641565483183955
431 1504559779150539544
432 1536053258511097771
433 1568131347225505549
434 1600803518734377862
435 1634079377756975284
436 1667968661803694632
437 1702481242702468018
438 1737627128139166002
439 1773416463212100986
440 1809859532000727428
441 1846966759148635895
442 1884748711460938415
443 1923216099516143030
444 1962379779292615895
445 2002250753809729712
446 2042840174783797733
447 2084159344298893012
448 2126219716492653033
449 2169032899257170289
450 2212610655955069836
451 2256964907150875296
452 2302107732357765234
453 2348051371799822286
454 2394808228189877868
455 2442390868523055750
456 2490812025886118234
457 2540084601282719131
458 2590221665474668189
459 2641236460839312082
460 2693142403243137529
461 2745953083931702572
462 2799682271436002503
463 2854343913495377392
464 2909952138997068631
465 2966521259932532373
466 3024065773370618210
467 3082600363447721900
468 3142139903375021420
469 3202699457462906090
470 3264294283162708982
471 3326939833125853298
472 3390651757280523872
473 3455445904925975423
474 3521338326844589659
475 3588345277431793806
476 3656483216843953611
477 3725768813164354344
478 3796218944587383801
479 3867850701621031788
480 3940681389307821045
481 4014728529464285049
482 4090009862939108616
483 4166543351890047704
484 4244347182079745302
485 4323439765190560774
486 4403839741158530512
487 4485565980526578238
488 4568637586817093782
489 4653073898923999651
490 4738894493524425193
491 4826119187510108650
492 4914768040438647885
493 5004861357004721060
494 5096419689531399035
495 5189463840481671752
496 5284014864990311363
497 5380094073416195357
498 5477723033915213438
499 5576923575033882404
500 5677717788323793776
501 5780128030977019426
502 5884176928482600954
503 5989887377304249066
504 6097282547579379708
505 6206385885839614215
506 6317221117752871239
507 6429812250887178726
508 6544183577496334719
509 6660359677327546272
510 6778365420451176269
511 6898225970112728452
512 7019966785607201473
513 7143613625175943297
514 7269192548926137796
515 7396729921773055888
516 7526252416405204090
517 7657787016272503870
518 7791361018597635700
519 7927002037410682230
520 8064738006607205522
521 8204597183029893803
522 8346608149573913717
523 8490799818316104578
524 8637201433668151649
525 8785842575553875996
526 8936753162610778991
527 9089963455415980064
528 9245504059736686831
529 9403405929805337253
530 9563700371619554010
531 9726419046267051804
532 9891593973275638836
533 10059257533988454234
534 10229442474964583742
535 10402181911405196514
536 10577509330605346392
537 10755458595431581583
538 10936063947825507187
539 11119360012333445566
540 11305381799662340083
541 11494164710262048280
542 11685744537934171105
543 11880157473467565340
544 12077440108300686925
545 12277629438210913417
546 12480762867030994368
547 12686878210392778952
548 12896013699498370718
549 13108207984918859894
550 13323500140420784216
551 13541929666820469806
552 13763536495866404174
553 13988360994149793971
554 14216443967043460673
555 14447826662669227930
556 14682550775893954869
557 14920658452354370196
558 15162192292510862499
559 15407195355730382712
560 15655711164398615259
561 15907783708061574957
562 16163457447596787318
563 16422777319414210452
564 16685788739687057336
565 16952537608612677778
566 17223070314703659970
567 17497433739109312090
568 17775675259967684980
569 18057842756788297495
570 18343984614865726687
571 18634149729724225558
572 18928387511593531687
573 19226747889916030608
574 19529281317885438389
575 19836038777017168436
576 20147071781750548121
577 20462432384083051409
578 20782173178236714236
579 21106347305356899968
580 21435008458243582850
581 21768210886115317934
582 22106009399406066556
583 22448459374595047014
584 22795616759069780682
585 23147538076022504379
586 23504280429380120397
587 23865901508767856178
588 24232459594506806217
589 24604013562645529356
590 24980622890025875223
591 25362347659383214160
592 25749248564481245575
593 26141386915281560245
594 26538824643148132690
595 26941624306086920332
596 27349849094020746748
597 27763562834099646922
598 28182829996046852998
599 28607715697540599634
600 29038285709631928656
601 29474606462198673311
602 29916745049435803019
603 30364769235382310126
604 30818747459484820763
605 31278748842198112520
606 31744843190622722249
607 32217101004179827916
608 32695593480323589029
609 33180392520291130777
610 33671570734890357624
611 34169201450325782712
612 34673358714062560038
613 35184117300728906982
614 35701552718057105376
615 36225741212863269918
616 36756759777066073350
617 37294686153744618435
618 37839598843235647385
619 38391577109270280010
620 38950700985150472477
621 39517051279965389188
622 40090709584847880907
623 40671758279271262888
624 41260280537386587379
625 41856360334400605501
626 42460082452994614126
627 43071532489784384004
628 43690796861821366016
629 44317962813135373058
630 44953118421318935690
631 45596352604153530314
632 46247755126277879276
633 46907416605898522919
634 47575428521542864247
635 48251883218854887494
636 48936873917433752527
637 49630494717715467648
638 50332840607897843997
639 51044007470908935396
640 51764092091419168113
641 52493192162897365665
642 53231406294710874420
643 53978834019269996400
644 54735575799216936330
645 55501733034659470622
646 56277408070449546628
647 57062704203507021142
648 57857725690188747778
649 58662577753703223499
650 59477366591571005221
651 60302199383131108066
652 61137184297093597489
653 61982430499138588156
654 62838048159561863103
655 63704148460967327360
656 64580843606006510879
657 65468246825165336261
658 66366472384598367434
659 67275635594010756092
660 68195852814588103364
661 69127241466974454842
662 70069920039298647758
663 71024008095249229762
664 71989626282198169416
665 72966896339373579183
666 73955941106081672355
667 74956884529978176030
668 75969851675389422915
669 76994968731683345400
670 78032363021690596017
671 79082163010176019068
672 80144498312360698877
673 81219499702494810793
674 82307299122481501744
675 83408029690552027816
676 84521825709992377006
677 85648822677921605974
678 86789157294122120296
679 87942967469922128398
680 89110392337130500030
681 90291572257024260819
682 91486648829388955121
683 92695764901612110074
684 93919064577830034437
685 95156693228128186484
686 96408797497795345907
687 97675525316631825368
688 98957025908311958027
689 100253449799801098061
690 101564948830827371878
691 102891676163408418420
692 104233786291433357640
693 105591435050300226930
694 106964779626609125970
695 108353978567911311162
696 109759191792514481508
697 111180580599344498487
698 112618307677863783183
699 114072537118046634614
700 115543434420411713911
701 117031166506111939696
702 118535901727082040709
703 120057809876244012436
704 121597062197770725193
705 123153831397407931825
706 124728291652854923884
707 126320618624204085856
708 127930989464439597714
709 129559582829995536782
710 131206578891373630604
711 132872159343820913222
712 134556507418067537978
713 136259807891125000667
714 137982247097145027581
715 139724012938339383698
716 141485294895960856985
717 143266284041345675500
718 145067173047017614695
719 146888156197854053040
720 148729429402314234807
721 150591190203729999573
722 152473637791659238722
723 154376973013302339948
724 156301398384981881484
725 158247118103685838506
726 160214338058674564886
727 162203265843151814194
728 164214110766000064576
729 166247083863580412863
730 168302397911597303995
731 170380267437028362574
732 172480908730119594091
733 174604539856446224104
734 176751380669039444377
735 178921652820579335724
736 181115579775654238037
737 183333386823086838713
738 185575301088327251432
739 187841551545913357976
740 190132369031998686518
741 192447986256948100550
742 194788637818001573360
743 197154560212006323710
744 199545991848217589110
745 201963173061168313827
746 204406346123608029513
747 206875755259511207082
748 209371646657155359213
749 211894268482269173604
750 214443870891250957851
751 217020706044457677576
752 219625028119564870179
753 222257093324997717341
754 224917159913433560158
755 227605488195376141540
756 230322340552801861264
757 233067981452878329826
758 235842677461755507994
759 238646697258429719722
760 241480311648680826844
761 244343793579082854727
762 247237418151088358823
763 250161462635186822822
764 253116206485137379871
765 256101931352276149088
766 259118921099898480365
767 262167461817716401220
768 265247841836391560225
769 268360351742143962305
770 271505284391436791972
771 274682934925737621328
772 277893600786356300442
773 281137581729359828478
774 284415179840564504724
775 287726699550605659446
776 291072447650085265266
777 294452733304797730539
778 297867868071034176981
779 301318165910965504578
780 304803943208104547585
781 308325518782847626204
782 311883213908095799311
783 315477352324956124384
784 319108260258523231567
785 322776266433741519589
786 326481702091348282042
787 330224901003898073308
788 334006199491868624212
789 337825936439848618266
790 341684453312807640158
791 345582094172448608930
792 349519205693643009080
793 353496137180949233615
794 357513240585214353875
795 361570870520259631742
796 365669384279650090643
797 369809141853548462552
798 373990505945653828993
799 378213841990225274844
800 382479518169190874541
801 386787905429342331081
802 391139377499615589024
803 395534310908457743496
804 399973085001280567998
805 404456081958000984630
806 408983686810668801144
807 413556287461182040046
808 418174274699090185774
809 422838042219485676787
810 427547986640983970209
811 432304507523792507482
812 437108007387868910293
813 441958891731168736852
814 446857569047983129411
815 451804450847366684728
816 456799951671655879995
817 461844489115078387565
818 466938483842453612630
819 472082359607984788820
820 477276543274142967512
821 482521464830643237458
822 487817557413513512162
823 493165257324256223258
824 498565004049103258964
825 504017240278364487511
826 509522411925870206271
827 515080968148507858134
828 520693361365853357511
829 526360047279897369168
830 532081484894866883925
831 537858136537142436084
832 543690467875271308281
833 549578947940077070289
834 555524049144865799132
835 561526247305729328704
836 567586021661945877922
837 573703854896478407278
838 579880233156571054492
839 586115646074444000806
840 592410586788087120298
841 598765551962152765435
842 605181041808948042925
843 611657560109526934770
844 618195614234882620265
845 624795715167240355532
846 631458377521451268023
847 638184119566487424272
848 644973463247038530023
849 651826934205210622709
850 658745061802327117106
851 665728379140832565836
852 672777423086299497244
853 679892734289538694026
854 687074857208813276838
855 694324340132156957970
856 701641735199796831024
857 709027598426681063391
858 716482489725111859179
859 724006972927484061102
860 731601615809129760699
861 739266990111269287112
862 747003671564068945513
863 754812239909805877132
864 762693278926140413701
865 770647376449496299993
866 778675124398549159000
867 786777118797823575160
868 794953959801399171910
869 803206251716726060710
870 811534603028550039552
871 819939626422947919838
872 828421938811473361382
873 836982161355413596163
874 845620919490157422329
875 854338842949674850826
876 863136565791108787901
877 872014726419479137604
878 880973967612499709291
879 890014936545508316008
880 899138284816510450515
881 908344668471336926589
882 917634748028915874126
883 927009188506659477444
884 936468659445965847072
885 946013834937836416194
886 955645393648609253802
887 965364018845808687498
888 975170398424111629772
889 985065224931431002471
890 995049195595116655063
891 1005123012348274173190
892 1015287381856201974895
893 1025543015542947092800
894 1035890629617980041405
895 1046330945102989169572
896 1056864687858794899153
897 1067492588612384251617
898 1078215382984066065428
899 1089033811514747307824
900 1099948619693330885546
901 1110960557984235359966
902 1122070381855036972964
903 1133278851804234390806
904 1144586733389136574178
905 1155994797253874183435
906 1167503819157534929029
907 1179114580002423277986
908 1190827865862444928209
909 1202644468011616463292
910 1214565182952700601439
911 1226590812445967452992
912 1238722163538082201983
913 1250960048591119628037
914 1263305285311705885866
915 1275758696780287960508
916 1288321111480531217380
917 1300993363328845467130
918 1313776291704039966190
919 1326670741477107774850
920 1339677563041139895592
921 1352797612341369615343
922 1366031750905347476227
923 1379380845873247300318
924 1392845770028303694819
925 1406427401827381465016
926 1420126625431677363281
927 1433944330737554603324
928 1447881413407510569821
929 1461938774901278154473
930 1476117322507061150480
931 1490417969372904138344
932 1504841634538197296846
933 1519389242965316573974
934 1534061725571399653512
935 1548860019260258153934
936 1563785066954426497182
937 1578837817627347885843
938 1594019226335697828177
939 1609330254251845651386
940 1624771868696454444453
941 1640345043171219872820
942 1656050757391748308115
943 1671889997320574717080
944 1687863755200320754795
945 1703973029586993508237
946 1720218825383425337158
947 1736602153872855260212
948 1753124032752652335208
949 1769785486168181483314
950 1786587544746812207986
951 1803531245632070660346
952 1820617632517935503684
953 1837847755683278030711
954 1855222672026446988143
955 1872743445099998564150
956 1890411145145571995159
957 1908226849128911249456
958 1926191640775033245989
959 1944306610603543067732
960 1962572855964096629929
961 1980991481072011264497
962 1999563597044024682828
963 2018290321934202780192
964 2037172780769996745906
965 2056212105588449944398
966 2075409435472555033260
967 2094765916587761785350
968 2114282702218636082970
969 2133960952805670553115
970 2153801835982247313757
971 2173806526611753302098
972 2193976206824848656697
973 2214312066056888626348
974 2234815301085499479559
975 2255487116068308889456
976 2276328722580831269911
977 2297341339654508539669
978 2318526193814906792226
979 2339884519120069350188
980 2361417557199026683820
981 2383126557290463674474
982 2405012776281544704566
983 2427077478746897056754
984 2449321936987753105952
985 2471747431071251788799
986 2494355248869899836187
987 2517146686101193255438
988 2540123046367399549707
989 2563285641195501163176
990 2586635790077300641593
991 2610174820509687998700
992 2633904068035070780085
993 2657824876281967316985
994 2681938597005763663560
995 2706246590129634712152
996 2730750223785629982038
997 2755450874355924578182
998 2780349926514235817488
999 2805448773267406021054
1000 2830748815997151971926