0 1
1 1
2 1
3 2
4 3
5 6
6 7
7 14
8 17
9 27
10 34
11 55
12 63
13 100
14 119
15 167
16 209
17 296
18 347
19 489
20 582
21 775
22 945
23 1254
24 1481
25 1951
26 2334
27 2980
28 3580
29 4564
30 5386
31 6841
32 8118
33 10085
34 12012
35 14862
36 17526
37 21636
38 25524
39 31082
40 36694
41 44582
42 52255
43 63260
44 74170
45 88931
46 104302
47 124753
48 145489
49 173510
50 202233
51 239644
52 279150
53 329930
54 382790
55 451214
56 523088
57 613662
58 710654
59 831819
60 960215
61 1121504
62 1293313
63 1504680
64 1733281
65 2012451
66 2312424
67 2679688
68 3075422
69 3553088
70 4072931
71 4697204
72 5373308
73 6185688
74 7067862
75 8116137
76 9263073
77 10619793
78 12098637
79 13848649
80 15758929
81 18001317
82 20461671
83 23338468
84 26486840
85 30167054
86 34199700
87 38883106
88 44032917
89 49995924
90 56539264
91 64112244
92 72428246
93 82003333
94 92544965
95 104650923
96 117958913
97 133230929
98 150024491
99 169219705
100 190364481
101 214481125
102 241013416
103 271248949
104 304519759
105 342309882
106 383946404
107 431149388
108 483099097
109 541946239
110 606711490
111 679881564
112 760475124
113 851376627
114 951410979
115 1064143190
116 1188193025
117 1327678864
118 1481242322
119 1653668354
120 1843344901
121 2056147995
122 2290199406
123 2552293656
124 2840640341
125 3163125394
126 3517664464
127 3913864294
128 4349336970
129 4835208607
130 5369300473
131 5964539503
132 6618433133
133 7346629008
134 8146361005
135 9035743962
136 10012493928
137 11097645015
138 12288683176
139 13610949894
140 15061786002
141 16670564452
142 18435596114
143 20390982601
144 22535115964
145 24908853438
146 27510866909
147 30388497676
148 33542329994
149 37027355199
150 40844909388
151 45060624581
152 49676999313
153 54770096354
154 60346052352
155 66493175249
156 73219832379
157 80630964768
158 88737930151
159 97662398622
160 107422354872
161 118159067158
162 129895517165
163 142798995929
164 156898969037
165 172389338725
166 189311484109
167 207890420101
168 228177664505
169 250438925014
170 274738437726
171 301384187867
172 330461236648
173 362326859894
174 397085476415
175 435157680996
176 476671748972
177 522114999373
178 571651609729
179 625846753119
180 684899778374
181 749474411780
182 819812793510
183 896683696020
184 980390346606
185 1071823752694
186 1171349388875
187 1280011041916
188 1398249075848
189 1527272091146
190 1667622727115
191 1820701100651
192 1987157008778
193 2168627105468
194 2365889510914
195 2580838169164
196 2814420785872
197 3068829878529
198 3345194440099
199 3646072432124
200 3972808423385
201 4328360978956
202 4714352404956
203 5134205283394
204 5589843976628
205 6085253814671
206 6622716459089
207 7206838152118
208 7840351424563
209 8528581301830
210 9274756118913
211 10085065885766
212 10963322928920
213 11916676539071
214 12949664776505
215 14070545636020
216 15284662370831
217 16601598101058
218 18027640570430
219 19573849975454
220 21247671770866
221 23061871173452
222 25025186789038
223 27152408925614
224 29453788931476
225 31946382488935
226 34642274945890
227 37561133582569
228 40717102313558
229 44132934884254
230 47825175497132
231 51820041207987
232 56136959762682
233 60806135438328
234 65850246158873
235 71304185390159
236 77194410589366
237 83561090077219
238 90435185988020
239 97862933703584
240 105880386468546
241 114540884553037
242 123886386928262
243 133978241340561
244 144865401175530
245 156618412339553
246 169294149591634
247 182973889853436
248 197723674741155
249 213636896482154
250 230790391035061
251 249291451168558
252 269229155521875
253 290726957914802
254 313888077442369
255 338854233841510
256 365745215792182
257 394723676655356
258 425928214937778
259 459545750427024
260 495736563165711
261 534715024020909
262 576666710407663
263 621837416509614
264 670441458194866
265 722760953360435
266 779043282907011
267 839611680370887
268 904751959275662
269 974834369944624
270 1050188397167212
271 1131238503938605
272 1218364334262444
273 1312051736671997
274 1412738467528433
275 1520980492397948
276 1637281604567028
277 1762278433057268
278 1896550492641688
279 2040825770564871
280 2195771245244582
281 2362219145337710
282 2540935826811517
283 2732873183547534
284 2938911353636232
285 3160137761883747
286 3397563621000736
287 3652430836026456
288 3925899502867946
289 4219388528586798
290 4534228217332188
291 4872037923241152
292 5234343552701070
293 5622992691950604
294 6039733343346664
295 6486674126247262
296 6965816594776317
297 7479564909277729
298 8030211357587839
299 8620496275463670
300 9253041892162945
301 9930972392340226
302 10657286171924256
303 11435541863340976
304 12269168332940835
305 13162217893936193
306 14118607653917898
307 15142952738857193
308 16239726179078630
309 17414179861898343
310 18671421805124919
311 20017426762576944
312 21458022500587875
313 23000006655487336
314 24650025519865720
315 26415807289646979
316 28304931589217198
317 30326181989842963
318 32488195304791687
319 34800954869436210
320 37274298336855330
321 39919565095850600
322 42747959876781847
323 45772358543577242
324 49005513238216549
325 52462044226814132
326 56156459313878358
327 60105349297720302
328 64325217689639238
329 68834885945949082
330 73653114863019797
331 78801255302666614
332 84300626301402537
333 90175434300646393
334 96449902301782657
335 103151466319055630
336 110307631459939199
337 117949491546113971
338 126108267394868905
339 134819179771924890
340 144117661756180695
341 154043597379569133
342 164637176829522138
343 175943559810249228
344 188008316556793350
345 200882555219985451
346 214617937416426403
347 229272286871217149
348 244904139142114565
349 261578907351144124
350 279362893321729004
351 298330061735045020
352 318555497072463676
353 340122810048577427
354 363116988451036480
355 387632532914332012
356 413765609231736704
357 441622980275449351
358 471313438421645659
359 502957566506000019
360 536678383504543784
361 572612058898037069
362 610897654277472319
363 651688877941048821
364 695142893581754984
365 741433159877895989
366 790737220674394378
367 843250788562528426
368 899174367933207710
369 958728695359999777
370 1022140156536503128
371 1089657644424069837
372 1161536660576630070
373 1238057794119125084
374 1319509319716418274
375 1406207443390240396
376 1498477345248835493
377 1596675274490752126
378 1701167897184113917
379 1812356499739472949
380 1930654404613798061
381 2056513471422769508
382 2190399511722664478
383 2332821198543892335
384 2484303302639224847
385 2645418340677677756
386 2816757334590837322
387 2998964442901180297
388 3192705152410790978
389 3398704041358160274
390 3617710177645984578
391 3850538434667427635
392 4098031721055084095
393 4361106164797744608
394 4640710055869744984
395 4937873096774342999
396 5253661772432466570
397 5589233202595404487
398 5945786468635442471
399 6324621475157050374
400 6727086078726253400
401 7154640222653942320
402 7608798506829859609
403 8091200276484458639
404 8603547044781768974
405 9147679059805280209
406 9725507379536022982
407 10339097267123925549
408 10990594463675114073
409 11682316277192317779
410 12416671317876869416
411 13196258955827790684
412 14023782260531139301
413 14902156290309117134
414 15834413665357693447
415 16823822787115897069
416 17873785129033641749
417 18987964253720714660
418 20170174490224604814
419 21424521360255636319
420 22755280926388212619
421 24167053021441363960
422 25664630128771829078
423 27253164529559732504
424 28938026293377592874
425 30724985147064881791
426 32620056682293399789
427 34629700713902454415
428 36760654291735601411
429 39020147979846235739
430 41415725136522459356
431 43955477170518116533
432 46647847976542757848
433 49501890409405150714
434 52527054127508839258
435 55733465119688545372
436 59131696280987101971
437 62733071376043077471
438 66549416965599269305
439 70593393646562135509
440 74878227171147807238
441 79418069316053225555
442 84227707345858311585
443 89322956321353645666
444 94720345198477381649
445 100437544171702851673
446 106493024752830192965
447 112906525162168748152
448 119698683328168530923
449 126891542690981417999
450 134508156014280571023
451 142573136155347359591
452 151112227428790991156
453 160152905199493091001
454 169723913485324458394
455 179855916453892127920
456 190580999674911302861
457 201933379285114688628
458 213948862899798184876
459 226665621381061006261
460 240123607787613017330
461 254365395758574199974
462 269435553332554737656
463 285381555241961986286
464 302253106734427965449
465 320103136086418104945
466 338987066443389994219
467 358963893768162876612
468 380095402838314499081
469 402447339861708795457
470 426088566711374353498
471 451092336274465135093
472 477535382512271452064
473 505499305314204566242
474 535069591701765406095
475 566337121865700946305
476 599397114345459105104
477 634350763556124300001
478 671304106033798103646
479 710369798236628238004
480 751665898205206080955
481 795317798414758210443
482 841456914201939096416
483 890222784833765466002
484 941761665226554546623
485 996228806608440180076
486 1053786944754300101315
487 1114608778936426484247
488 1178875346288043306184
489 1246778715858473923733
490 1318520244993703607701
491 1394313503224447816938
492 1474382402586742592475
493 1558964374994977801312
494 1648308364092282556875
495 1742678277575201872269
496 1842350835776643209585
497 1947619317987653366788
498 2058791258216653596821
499 2176192515439287461624
500 2300164801780579265280
501 2431070104101396907772
502 2569288039085647120721
503 2715220650772245313219
504 2869289581341515847067
505 3031941282464198651610
506 3203643984369244048652
507 3384893355993910888142
508 3576209266106163347003
509 3778141924035171537109
510 3991268419828920401038
511 4216199393504633912779
512 4453575333821374076596
513 4704073820700791037034
514 4968405575764449664417
515 5247322318923607545020
516 5541612555749568290063
517 5852110108921301536231
518 6179689618692327291343
519 6525275806187325928218
520 6889838679667303068332
521 7274403582551733377345
522 7680046088603945236520
523 8107902911527474124145
524 8559166461765041788979
525 9035096690393497790408
526 9537015300152823511922
527 10066318591787500099448
528 10624471310587280065891
529 11213020592521695110325
530 11833589415244962779599
531 12487891736845405972430
532 13177725544423885783485
533 13904989273245567290329
534 14671674432657401255924
535 15479883428970329919564
536 16331821733969593177426
537 17229817229991363967477
538 18176311915556491490408
539 19173882885687443690737
540 20225233553526277479244
541 21333216422211708570597
542 22500823784338852226886
543 23731212436596895726572
544 25027693854446929293969
545 26393760995004841021908
546 27833077926008223622609
547 29349508915133986374840
548 30947107472467909928423
549 32630147919266549243346
550 34403113846223951177282
551 36270732348871285123698
552 38237961882668817552279
553 40310029416409230738458
554 42492417642119287815330
555 44790905292834514353061
556 47211553717596294448751
557 49760750604354432757375
558 52445195905749110369789
559 55271949286085137652594
560 58248415356964780133229
561 61382395162881764026497
562 64682070749323798042742
563 68156060996536236172173
564 71813405514488757081958
565 75663625229608204067003
566 79716705570469946974063
567 83983162209113588401379
568 88474023578566024051681
569 93200902166643654187579
570 98175976374227529994345
571 103412067875563710992445
572 108922622791483380615941
573 114721795629039707557837
574 120824429837889707704281
575 127246148840550902415899
576 134003336003815833365992
577 141113233412529912746557
578 148593921248731361598507
579 156464424963914190342589
580 164744694173086072489744
581 173455718882380072756765
582 182619507964652877936881
583 192259215272078129196291
584 202399117716258025826486
585 213064752102302039179334
586 224282892976054139084025
587 236081701023305130945920
588 248490700802007932041985
589 261540941761240642258379
590 275264975928258564885197
591 289697032615758293096440
592 304872996304125221835743
593 320830596120295386610806
594 337609384107154893913738
595 355250940815001018707600
596 373798854098188467766387
597 393298942184237178724917
598 413799233346231557406365
599 435350207840317348269999
600 458004778751086720023542
601 481818554503286362923738
602 506849821122762434878551
603 533159827066351502620313
604 560812767396145305800578
605 589876092712500275864593
606 620420495686803284080284
607 652520246268116112057163
608 686253180963801807642894
609 721701066548095513207624
610 758949592792749523848576
611 798088766967999185881913
612 839212910673973898711148
613 882421087896683264554174
614 927817106536770982992600
615 975509982867668990772419
616 1025613948742348410067609
617 1078248955392080004474788
618 1133540687245176769300270
619 1191621108583631746910144
620 1252628484859304366199619
621 1316707975846611128211091
622 1384011665814000195981933
623 1454699206941558065145737
624 1528937859669231886140223
625 1606903190858351526001019
626 1688779125601182954029391
627 1774758704775348784731865
628 1865044150181096531946043
629 1959847686321528964647562
630 2059391620715441260509432
631 2163909235608484556362423
632 2273644885292816989085116
633 2388854963689847316850213
634 2509808021225849618239570
635 2636785814481958737354774
636 2770083445185161435999481
637 2910010499193691779017145
638 3056891210178277361710044
639 3211065695534063596012435
640 3372890148214072283599972
641 3542738177508596708707873
642 3721001032547026259731893
643 3908089057205582486668933
644 4104431948857935592070585
645 4310480337110796081168885
646 4526706082481815237428733
647 4753603989138067267826944
648 4991692148298292069407032
649 5241513796775816318851825
650 5503637710037677552973379
651 5778660218944957323611556
652 6067205658762882193469249
653 6369928557132709817142928
654 6687514145538062692316668
655 7020680733548743500414367
656 7370180289486050938547380
657 7736801016771315178971112
658 8121368012223626849888122
659 8524746061205131302394949
660 8947840382325790664584326
661 9391599660555044587641516
662 9857016887489146130592976
663 10345132652654305648612099
664 10857036090595123020358159
665 11393868451738992843157636
666 11956824168085985343222607
667 12547154728067493595496236
668 13166169873197145290777620
669 13815241802756296534280543
670 14495806516384902537283053
671 15209368375944215482120428
672 15957501609796316972039494
673 16741855262985451980947170
674 17564154879806158717507527
675 18426207875292255015552037
676 19329905415940993589123828
677 20277228247502764885900783
678 21270248794834942208630607
679 22311137485682880433064836
680 23402165091856945834549831
681 24545709591125523990663929
682 25744258775990534152393103
683 27000417698448800353553864
684 28316911574201635086270153
685 29696593860867266773960299
686 31142449487176500286573031
687 32657603618404785998520401
688 34245325245211081667480231
689 35909036693513349075394664
690 37652317609795368848791986
691 39478915279883795756623330
692 41392749049928567117607114
693 43397921522703122950029671
694 45498723459857416192432299
695 47699645928878014105189368
696 50005385735189186330915577
697 52420858601901549459613651
698 54951205183600700930574946
699 57601805366440004355780669
700 60378284923471130875171859
701 63286531028521032840985509
702 66332699616966810798579629
703 69523232218023552371130194
704 72864864089299367429907460
705 76364642479176086117452814
706 80029935613538846525546145
707 83868452507581852160341458
708 87888252888567177716430746
709 92097768690318501305952844
710 96505815001837146522424562
711 101121613386898733783653772
712 105954803960989950390096818
713 111015470688345108146842194
714 116314154696983107083759538
715 121861881722882918261513714
716 127670176780895217514341738
717 133751093937603121196377698
718 140117232471767910600760231
719 146781769170263852819573504
720 153758476121460908346226335
721 161061755750279477364285798
722 168706660398552571224376033
723 176708930330551730975328527
724 185085015274357343128741771
725 193852115645795728075329421
726 203028206237757219811202717
727 212632080937520072186590491
728 222683378765042311087588497
729 233202632378386665341530257
730 244211296687173519314976889
731 255731801462210865864937968
732 267787582767327338869788962
733 280403140023083872114273883
734 293604070518774497281034242
735 307417131305507569810679979
736 321870277081857274186497106
737 336992727319136467569459351
738 352815007836557965050823947
739 369369023603738655757458074
740 386688104345608679310975434
741 404807083499849876761235287
742 423762348231736507110582175
743 443591925059596733749014861
744 464335534689062925109432777
745 486034684872448234756971090
746 508732730503780313494477669
747 532474974319908735604886979
748 557308732748057036074771543
749 583283445101886813105090472
750 610450745711528638394135645
751 638864582333908382360557375
752 668581295136815535720812610
753 699659745096528995443154226
754 732161400470995546082935450
755 766150476015982082122832785
756 801694027632172204927808442
757 838862103313805798709299372
758 877727846708593825419769707
759 918367660781582472526655648
760 960861321106904692456371244
761 1005292153304074193879898919
762 1051747156945130326795512705
763 1100317197924192833381723499
764 1151097143933712394154962226
765 1204186073016036113185083000
766 1259687421663557188567336813
767 1317709210896221493177211632
768 1378364208123907957885388023
769 1441770172223648126550509164
770 1508050030393334089092710153
771 1577332143814679325212943663
772 1649750500854892232588661099
773 1725445005022910006140645611
774 1804561685983565788507354623
775 1887253011677361543335638332
776 1973678118728824767974417157
777 2064003150743253297438398620
778 2158401509851885923373200217
779 2257054223353982965849596933
780 2360150218280478608512935440
781 2467886718753771981897024410
782 2580469545602466498926375361
783 2698113546993629765111844784
784 2821042925334277680080131946
785 2949491703928193307643485517
786 3083704083578657855550072718
787 3223934948277725160271634797
788 3370450254118760395727490591
789 3523527577258167270747277483
790 3683456538002470218836962759
791 3850539394533563993492037145
792 4025091505264693804496853281
793 4207441972141088280732936265
794 4397934144608243625318355361
795 4596926316594863794211385023
796 4804792275760007400354685143
797 5021922058584382849328869241
798 5248722548857213162745697601
799 5485618295704258477069859000
800 5733052165594332345293507063
801 5991486228507162815085352696
802 6261402468147061110426567165
803 6543303741858946450899099794
804 6837714554113255783155939388
805 7145182096283051867483877120
806 7466277088872405774728043267
807 7801594907742985866579055816
808 8151756501072052753173818490
809 8517409609130970421571757564
810 8899229762440099074761188154
811 9297921602834531195851268717
812 9714219969804447262932549928
813 10148891331186113977044055256
814 10602734965324093954092578106
815 11076584510377034212592146128
816 11571309250551968891951057543
817 12087815793808125625662099957
818 12627049471078373600869426920
819 13189996152917647142848870244
820 13777683771442974226526055678
821 14391184287298069419105856948
822 15031615344825452929201128581
823 15700142401714084441377203062
824 16397980528763802215477974389
825 17126396715548837264703950730
826 17886711827163254479243558569
827 18680303100276877491522988119
828 19508606270245503194146237038
829 20373118273183778133458320224
830 21275399557900942473532640315
831 22217077010836498353746354042
832 23199846468577376374301541837
833 24225475883821531493043940747
834 25295808055496971995276740172
835 26412764055483013889288337581
836 27578346194719785785421900581
837 28794641731959718896498793928
838 30063826095886461011830839759
839 31388166898835484452139885749
840 32770027436546372338503958073
841 34211871031752548278772279888
842 35716264834926924666205949453
843 37285884524588217529716056857
844 38923518434451347593010958421
845 40632072639400673501688362752
846 42414575436491388855031013523
847 44274182847997609940243810740
848 46214183485911263337111395373
849 48238004505929214016341873463
850 50349216887676226755714776570
851 52551541876147039010384540096
852 54848856712456910110630950336
853 57245201602333536237114022804
854 59744785934984263799345483645
855 62351995821328289549214665890
856 65071400841813164301778429941
857 67907762200418949875852866530
858 70866040045516561528825668347
859 73951402289532005957331751319
860 77169232550461935052604947666
861 80525139690984365845367519719
862 84024966432322502062338217914
863 87674799670795146675673859586
864 91480979819839556465408655127
865 95450111966823517852557061709
866 99589076003488674761281508701
867 103905038690751751630955470835
868 108405464642948565635990489066
869 113098129373644577851390624830
870 117991131204260859400878147498
871 123092905369958432777073116263
872 128412236928844815560903071613
873 133958276013165067631474547205
874 139740551821713133103288201958
875 145768989108216486623913949627
876 152053923346136426259971157420
877 158606118553696417431847045995
878 165436783727338538287733084826
879 172557592110596595640399593233
880 179980699000537800659899968497
881 187718762576041099642814429719
882 195784963189819274497495090573
883 204193025881123335512830178820
884 212957241274863147828449880089
885 222092489913491293654985524756
886 231614264894849866498719363589
887 241538698168481624527315178360
888 251882585054237182690972235039
889 262663412660090356150591130786
890 273899386434770484831630103969
891 285609460876371100329971140022
892 297813368284942663258083412747
893 310531651944349233813920387586
894 323785697253846699038009275474
895 337597767580427104875211164180
896 351991037962529948002382575486
897 366989633845426981227475641638
898 382618667566085844135279775198
899 398904280200653395819254506494
900 415873681055941613055558157401
901 433555192876539531087228925250
902 451978294586135389058655134879
903 471173670120975657394823185114
904 491173254684108184360944777105
905 512010287492584844397010000521
906 533719361828367573793669519606
907 556336482009740068071399064007
908 579899117544894291232589876332
909 604446264662044938647911012624
910 630018504896577694351235316807
911 656658071540248718776792346784
912 684408913018693965939359057446
913 713316764648893234122598287227
914 743429217191781833757860928935
915 774795794337227765820237531006
916 807468026847580930483059333540
917 841499536221802614331267507950
918 876946114878280190350111685535
919 913865816485680423486405066749
920 952319042668379305317272672410
921 992368640529214594388885554728
922 1034079996399743936673188711866
923 1077521141120571341397398689227
924 1122762851399350300130831626885
925 1169878763459173894661608961240
926 1218945482611100756137775012115
927 1270042705928095150029707279574
928 1323253340687400818403823541083
929 1378663636778122744608506419569
930 1436363314719724088153209224954
931 1496445708567209282029231684781
932 1559007904266909131592496029922
933 1624150893881922958818058316308
934 1691979725106966609636048223046
935 1762603667699924358850150942695
936 1836136375041263081882925636615
937 1912696063727159213943851080854
938 1992405688127622810098555925311
939 2075393134169931709479060559816
940 2161791407925235672917011032597
941 2251738844689892053427982289843
942 2345379312709973388055798585966
943 2442862438754801545567295047060
944 2544343828174555267071291744633
945 2649985308251694352923192034897
946 2759955165881174170088860959205
947 2874428410083806869907819978391
948 2993587028698075260885583235343
949 3117620271547411926979120867461
950 3246724927639709982407544304924
951 3381105630594438285828298284897
952 3520975157963490692824162540587
953 3666554760646647127956344306189
954 3818074486071570591445152045006
955 3975773533460423033024973934761
956 4139900602740467683918978558680
957 4310714277666602413581236593306
958 4488483402480443324979011669296
959 4673487495046245204230531806080
960 4866017153431208074213776483433
961 5066374501379277964399166412721
962 5274873627152072299571386941328
963 5491841063841806580887369053564
964 5717616262994517070512744084292
965 5952552112453464576684381204319
966 6197015447479354408918010938893
967 6451387609023188709970129910796
968 6716064995265853347881651343313
969 6991459663439340397077315347574
970 7277999924934875077233213583468
971 7576130994027952290703815097176
972 7886315629944593146872556356668
973 8209034836103596418044917805429
974 8544788552789120681805100230501
975 8894096410797094823330639609889
976 9257498478644361325163042017561
977 9635556074800288403768986034252
978 10028852573661960546364140543715
979 10437994280872373856676012883755
980 10863611302612984561150900035616
981 11306358488849864682016828098836
982 11766916370845450458577117173076
983 12245992177539511607834487453051
984 12744320846554181566988006033822
985 13262666119314202548127912943472
986 13801821631219556556084459190712
987 14362612091531794232217651763149
988 14945894458823997794086891911031
989 15552559212113915719970799294385
990 16183531618163723362652740614046
991 16839773100833956878604913215476
992 17522282607302973674132806177438
993 18232098083140018916597409679498
994 18970297945054834146654577495749
995 19738002669751617838450919800305
996 20536376381394095928098407289855
997 21366628562913781584556907794728
998 22230015766993672561386454443929
999 23127843459154809289445464079647
1000 24061467861732457437145017272868