0 1
1 1
2 2
3 4
4 6
5 10
6 14
7 21
8 27
9 40
10 52
11 70
12 92
13 124
14 156
15 206
16 264
17 335
18 425
19 539
20 673
21 847
22 1052
23 1300
24 1611
25 1990
26 2433
27 2977
28 3638
29 4420
30 5367
31 6496
32 7829
33 9439
34 11341
35 13590
36 16270
37 19425
38 23135
39 27525
40 32697
41 38745
42 45844
43 54168
44 63875
45 75247
46 88493
47 103892
48 121846
49 142701
50 166871
51 194920
52 227388
53 264927
54 308327
55 358418
56 416133
57 482653
58 559199
59 647169
60 748266
61 864284
62 997217
63 1149589
64 1323983
65 1523379
66 1751275
67 2011469
68 2308282
69 2646704
70 3032213
71 3470966
72 3970073
73 4537403
74 5181687
75 5913111
76 6742704
77 7682965
78 8748159
79 9953972
80 11318026
81 12860329
82 14602930
83 16570607
84 18791295
85 21295951
86 24119057
87 27299587
88 30880661
89 34910334
90 39442563
91 44537158
92 50260637
93 56687697
94 63900815
95 71991911
96 81063574
97 91229392
98 102615603
99 115362987
100 129627155
101 145580928
102 163416495
103 183346572
104 205606668
105 230458660
106 258191690
107 289126063
108 323616992
109 362056687
110 404878904
111 452564074
112 505642179
113 564699050
114 630382137
115 703405824
116 784558054
117 874709513
118 974819245
119 1085944851
120 1209252879
121 1346027747
122 1497683950
123 1665780693
124 1852032612
125 2058326974
126 2286740884
127 2539557755
128 2819287801
129 3128691749
130 3470801208
131 3848946824
132 4266787025
133 4728337513
134 5238004716
135 5800625933
136 6421504837
137 7106458161
138 7861864161
139 8694712133
140 9612659845
141 10624098473
142 11738214692
143 12965067743
144 14315669097
145 15802067502
146 17437443209
147 19236215591
148 21214148316
149 23388474956
150 25778032111
151 28403400392
152 31287060603
153 34453569072
154 37929733892
155 41744820899
156 45930770967
157 50522433899
158 55557824386
159 61078406538
160 67129386387
161 73760045861
162 81024097763
163 88980068631
164 97691714696
165 107228483389
166 117665991676
167 129086566104
168 141579818252
169 155243265109
170 170183003539
171 186514451649
172 204363126186
173 223865510208
174 245169978200
175 268437797921
176 293844212800
177 321579628570
178 351850866291
179 384882546585
180 420918572118
181 460223728753
182 503085415621
183 549815533711
184 600752487095
185 656263384682
186 716746395747
187 782633297531
188 854392220573
189 932530636949
190 1017598540230
191 1110191922234
192 1210956499192
193 1320591736021
194 1439855179325
195 1569567162652
196 1710615822788
197 1863962564553
198 2030647919200
199 2211797865514
200 2408630632003
201 2622464063693
202 2854723490650
203 3106950272903
204 3380810958353
205 3678107161063
206 4000786177826
207 4350952466819
208 4730879919824
209 5143025150963
210 5590041745888
211 6074795610334
212 6600381457628
213 7170140604486
214 7787680006461
215 8456892829900
216 9181980501244
217 9967476440667
218 10818271537411
219 11739641603781
220 12737276755567
221 13817313099649
222 14986366693405
223 16251570062146
224 17620611369512
225 19101776579202
226 20703994573700
227 22436885743462
228 24310814039373
229 26336942894341
230 28527295176159
231 30894817636245
232 33453449876407
233 36218198514987
234 39205216608639
235 42431888907912
236 45916923196875
237 49680448380128
238 53744119425177
239 58131230074042
240 62866833495489
241 67977871685947
242 73493314026798
243 79444305929044
244 85864327814148
245 92789365688345
246 100258093639730
247 108312069417968
248 116995943728954
249 126357684556378
250 136448817006728
251 147324680377236
252 159044703068178
253 171672696971763
254 185277172321654
255 199931674869750
256 215715146237372
257 232712309802878
258 251014083164808
259 270718019499664
260 291928779333439
261 314758635356338
262 339328011706571
263 365766060982433
264 394211280675582
265 424812172328909
266 457727945716722
267 493129271785155
268 531199086628892
269 572133451042687
270 616142468333683
271 663451265072621
272 714301038258478
273 768950174199662
274 827675442660940
275 890773272635341
276 958561113874466
277 1031378890844495
278 1109590554297252
279 1193585737977050
280 1283781525926755
281 1380624339284729
282 1484591948890215
283 1596195623158906
284 1715982418931590
285 1844537625992253
286 1982487373489786
287 2130501410781388
288 2289296072177290
289 2459637439032471
290 2642344710568212
291 2838293798577481
292 3048421158342647
293 3273727873377778
294 3515284008097710
295 3774233247521563
296 4051797840677651
297 4349283869239192
298 4668086859623489
299 5009697763373240
300 5375709326634075
301 5767822875820789
302 6187855543807810
303 6637747967151333
304 7119572481121080
305 7635541847549775
306 8188018545952923
307 8779524666343603
308 9412752439054180
309 10090575444777010
310 10816060543902573
311 11592480574490140
312 12423327863192813
313 13312328603542699
314 14263458152607856
315 15280957307194770
316 16369349616210597
317 17533459798767917
318 18778433332136412
319 20109757286471915
320 21533282479747093
321 23055247039294001
322 24682301451654792
323 26421535198733453
324 28280505072528334
325 30267265277117285
326 32390399423080969
327 34659054536341691
328 37082977198663661
329 39672551957749115
330 42438842139191127
331 45393633213479372
332 48549478868278690
333 51919749957839209
334 55518686497127447
335 59361452894621793
336 63464196612501012
337 67844110469928645
338 72519498803161902
339 77509847724251439
340 82835899716971023
341 88519732842263881
342 94584844821583958
343 101056242301267979
344 107960535601037067
345 115326039286221029
346 123182878902215494
347 131563104252980965
348 140500809603834351
349 150032261233817430
350 160196032766213215
351 171033148753265290
352 182587236993779034
353 194904690118107159
354 208034836977549394
355 222030124433790035
356 236946310152457627
357 252842667067108586
358 269782200188312467
359 287831876504903194
360 307062868733580295
361 327550813749430714
362 349376086546589745
363 372624090659801298
364 397385565995050538
365 423756915111712860
366 451840549017821993
367 481745253640207792
368 513586578160000679
369 547487246511362665
370 583577593372291597
371 621996026099476646
372 662889514093624451
373 706414107213234168
374 752735484901500723
375 802029537832741697
376 854482983935652770
377 910294020812346126
378 969673016628905090
379 1032843241726615412
380 1100041643275868273
381 1171519665482157301
382 1247544117933626670
383 1328398094892361676
384 1414381948420879120
385 1505814318464646616
386 1603033223121596344
387 1706397212578322998
388 1816286590314298200
389 1933104705456393249
390 2057279320301892774
391 2189264057332045711
392 2329539930201701081
393 2478616963521048435
394 2637035906426403653
395 2805370045309059006
396 2984227121273094760
397 3174251358296866743
398 3376125608311354290
399 3590573619848637614
400 3818362437178252582
401 4060304937342951404
402 4317262512800447072
403 4590147907915054239
404 4879928217886819530
405 5187628059292717044
406 5514332921795773426
407 5861192711234841422
408 6229425494732871538
409 6620321459177878797
410 7035247094921031167
411 7475649617319952201
412 7943061639299489757
413 8439106108977218528
414 8965501527007024944
415 9524067459250381352
416 10116730361078011222
417 10745529730652354543
418 11412624609310627143
419 12120300448335605016
420 12870976362257735506
421 13667212790109769997
422 14511719587028356612
423 15407364569998447831
424 16357182542616354641
425 17364384825306360015
426 18432369318626768828
427 19564731129009884400
428 20765273787638193259
429 22038021095034849812
430 23387229625452970220
431 24817401927231746826
432 26333300456961329010
433 27939962287584227767
434 29642714632445406940
435 31447191229814748887
436 33359349634495086536
437 35385489465915280083
438 37532271664427732345
439 39806738810588903639
440 42216336564804276170
441 44768936288082159811
442 47472858907525525698
443 50336900093917768971
444 53370356821958487385
445 56583055387799956679
446 59985380962114919508
447 63588308761429411673
448 67403436924419883351
449 71443021184859095650
450 75720011437291136883
451 80248090296995542936
452 85041713760706190460
453 90116154080578848601
454 95487544969331927253
455 101172929261153041711
456 107190309158979140624
457 113558699206089999051
458 120298182126653796089
459 127429967687930669843
460 134976454744251903774
461 142961296631808669770
462 151409470091487770850
463 160347347906798060461
464 169802775453050783219
465 179805151364747850191
466 190385512538215619647
467 201576623698439932764
468 213413071770211045598
469 225931365306796252376
470 239170039241737306717
471 253169765243794745196
472 267973467968741139639
473 283626447517627138879
474 300176508426264145377
475 317674095528181186506
476 336172437050072993401
477 355727695318027049333
478 376399125471326686564
479 398249242601884513360
480 421343997757805053303
481 445752963272956834532
482 471549527907068257322
483 498811102306585631746
484 527619335321514266894
485 558060341741823586615
486 590224942044573803850
487 624208914774112621819
488 660113262208187339944
489 698044489997128069777
490 738114901496899931791
491 780442907554627498396
492 825153352542307441447
493 872377857475998391641
494 922255181098779352725
495 974931599851489842272
496 1030561307700470187902
497 1089306836841874227648
498 1151339500351965540394
499 1216839857908169290351
500 1285998205760665574717
501 1359015092195181149237
502 1436101859788256164287
503 1517481215823267208663
504 1603387832302282437149
505 1694068977062476001931
506 1789785177579498144910
507 1890810919121158081730
508 1997435378995909273273
509 2109963198729702951716
510 2228715296094122687066
511 2354029719006599704512
512 2486262543421977232132
513 2625788817442263112389
514 2773003553979796731713
515 2928322774427355893684
516 3092184605908024730035
517 3265050434807608557940
518 3447406119423763832949
519 3639763264708789767334
520 3842660562227570113437
521 4056665198609101210900
522 4282374335929047938079
523 4520416667633141615962
524 4771454053786233919213
525 5036183239621128360691
526 5315337661553742058607
527 5609689345039153392589
528 5920050898854669543841
529 6247277610624421304546
530 6592269648632709874126
531 6955974375224057145524
532 7339388777343683042445
533 7743562020047502937002
534 8169598129091818956444
535 8618658809015118231971
536 9091966403433372810630
537 9590807004601946330370
538 10116533719636641033953
539 10670570101150576623548
540 11254413750436426609263
541 11869640101723094440838
542 12517906396445525730908
543 13200955856904717590661
544 13920622069144751166241
545 14678833585354719326548
546 15477618756597215883203
547 16319110807192678256642
548 17205553162631093113438
549 18139305043461242698999
550 19122847338202762673097
551 20158788768961031333332
552 21249872364077956767238
553 22398982252847697310507
554 23609150798043069570908
555 24883566082761423448345
556 26225579768885019615584
557 27638715345287580277422
558 29126676784781119193400
559 30693357629714158144732
560 32342850527078494305513
561 34079457234986674894601
562 35907699123419722331867
563 37832328193246159126517
564 39858338638650774375668
565 41990978979318459223172
566 44235764789965518861087
567 46598492056133082931366
568 49085251186524113838499
569 51702441713614134856170
570 54456787715763797093414
571 57355353995648044419119
572 60405563051458340123146
573 63615212879072048068903
574 66992495645181706411844
575 70546017273279945063594
576 74284817986366141785647
577 78218393852324486819682
578 82356719380081525459678
579 86710271216932274691257
580 91290052999787759112276
581 96107621415593982287205
582 101175113528760662309518
583 106505275436171185859397
584 112111492313179351233179
585 118007819916989523132050
586 124209017616919303364707
587 130730583024317056177465
588 137588788298302464082640
589 144800718207079523320599
590 152384310028288142361127
591 160358395375778290517465
592 168742744044257704772211
593 177558109967549951527550
594 186826279390649473551784
595 196570121360447641603124
596 206813640644872172186382
597 217582033195308326871004
598 228901744272495388923315
599 240800529361697387023052
600 253307518008770989504225
601 266453280714882046076420
602 280269899033991377541590
603 294791039023930112232574
604 310052028208848820763230
605 326089936218148312134524
606 342943659274613360277857
607 360654008712474816822259
608 379263803714448355932552
609 398817968465545125806912
610 419363633930546178849556
611 440950244471590686738083
612 463629669532269093072750
613 487456320625055044649153
614 512487273869773147909559
615 538782398342207423388782
616 566404490503824067045290
617 595419414996043327140142
618 625896252095461093718182
619 657907452140030460364197
620 691528997250376520368553
621 726840570685279969665246
622 763925734185833325950034
623 802872113679002484267404
624 843771593728218084459349
625 886720521136339645362428
626 931819918124780009933046
627 979175705531920255450260
628 1028898936494082276640662
629 1081106041093440027034111
630 1135919082479232640472341
631 1193466024991686436986831
632 1253881014842047045121181
633 1317304673927270289892584
634 1383884407384106996702395
635 1453774725514757473270163
636 1527137580744847188198668
637 1604142720304413918892863
638 1684968055353776631852543
639 1769800047308817071735139
640 1858834112154221779255269
641 1952275043568859094794930
642 2050337455724573025785598
643 2153246246658532978627663
644 2261237083159753061410584
645 2374556908152770310806676
646 2493464471605612856954122
647 2618230886035397427298143
648 2749140207733030961226467
649 2886490044878872365688552
650 3030592193773695621622871
651 3181773304464220424734706
652 3340375577099697090436802
653 3506757490415905152483890
654 3681294563805301231639392
655 3864380154497309679526486
656 4056426291440738940505605
657 4257864547551426409253284
658 4469146952062313014375779
659 4690746944790649497182101
660 4923160374217783770714579
661 5166906541361422578960060
662 5422529291508244791621859
663 5690598155966742741634336
664 5971709546096025560459657
665 6266488001966538903323171
666 6575587498113079550351877
667 6899692808949646881369288
668 7239520936529417925676937
669 7595822603452024650193422
670 7969383813844194520190663
671 8361027485469289987008087
672 8771615156156191500953202
673 9202048767878951533885426
674 9653272531965549208694695
675 10126274879067573002176793
676 10622090497682601717310109
677 11141802465188161205197357
678 11686544475520256628536686
679 12257503167811382744392230
680 12855920560492454521173141
681 13483096595561087767322487
682 14140391797924958351462122
683 14829230054944441620364728
684 15551101521523249637208453
685 16307565656330260766564162
686 17100254394980053333456859
687 17930875466254785526672101
688 18801215857715898723929432
689 19713145437331697251626299
690 20668620738036075265957847
691 21669688912435624396308909
692 22718491865196981348202753
693 23817270570974733665782234
694 24968369586082429861041591
695 26174241762466484962811225
696 27437453172914986067699721
697 28760688256821914319701308
698 30146755196232085778545180
699 31598591532314586173708040
700 33119270032852636160318864
701 34712004821797180532563245
702 36380157782410074678717211
703 38127245246022150338988913
704 39956944978951742511699273
705 41873103480672157706665421
706 43879743606882160643198766
707 45981072531723674116010719
708 48181490064005662137459746
709 50485597332934543878647580
710 52898205859519650231227431
711 55424347030519255302041528
712 58069281992518829392806883
713 60838511984490577627738010
714 63737789127972339675853188
715 66773127694826890234190070
716 69950815873399952945841148
717 73277428054789335608059710
718 76759837661868939763385793
719 80405230544682678575171951
720 84221118966835054503720511
721 88215356208560171988080272
722 92396151813249880002286458
723 96772087505367614492715500
724 101352133808868028414994375
725 106145667396486928435638292
726 111162489201562169673421937
727 116412843325397490263000537
728 121907436774588702000536406
729 127657460064198924119393665
730 133674608724197690131770683
731 139971105748171765371616097
732 146559725024974556324361628
733 153453815795710343328347099
734 160667328180250554093855174
735 168214839819356478935569085
736 176111583680437709870863908
737 184373477077013048248900438
738 193017151954062349837903223
739 202059986493668989587697060
740 211520138097655218346362710
741 221416577806312238292752334
742 231769126214825456553351989
743 242598490951599071760175436
744 253926305785395258379824199
745 265775171431028147802830478
746 278168698126294186862636311
747 291131550055885139812985378
748 304689491701220907754287600
749 318869436198463816803232798
750 333699495790437304876622506
751 349209034461777889377370641
752 365428722850403509398348594
753 382390595532292233423600512
754 400128110780636876245740913
755 418676212904682311454468074
756 438071397277967576192217695
757 458351778170293928844557003
758 479557159502527673405790846
759 501729108648333181116301798
760 524911033412122453612074944
761 549148262317913909721297574
762 574488128349420703512753934
763 600980056287549729446935974
764 628675653797592995613317030
765 657628806424746039263068160
766 687895776663200615932262317
767 719535307270944739447472805
768 752608729009570066236130963
769 787180072995849331116899953
770 823316187859613594305993990
771 861086861910546242686132229
772 900564950524927368373310505
773 941826508972125275563577101
774 984950930909751691020011926
775 1030021092785891970638077930
776 1077123504396702427306144284
777 1126348465857953374343109154
778 1177790231259800863957077711
779 1231547179285213362266455751
780 1287721991084075153736921130
781 1346421835707058616387785583
782 1407758563415917313306569731
783 1471848907199925262093724795
784 1538814692841790780847007359
785 1608783057890531913632476495
786 1681886679913532067835239104
787 1758264014415327020402543711
788 1838059542826626917182544355
789 1921424030983679221407950867
790 2008514798535351532867001630
791 2099495999733288946768122114
792 2194538916079201768167728754
793 2293822261322800485069410407
794 2397532499324140571428175742
795 2505864175315207036597695453
796 2619020261117484490490659762
797 2737212514895062719620607442
798 2860661856046549551153051400
799 2989598755863744962849043419
800 3124263644610704728635003486
801 3264907335703534397721594564
802 3411791467699039621565690032
803 3565188964829266238860686077
804 3725384516849030623863371305
805 3892675078994820773961469417
806 4067370392885982235176738298
807 4249793529232947379561588724
808 4440281453252466054529744740
809 4639185613726411650199709947
810 4846872556678817262224153766
811 5063724564685407904920794251
812 5290140322871088859674797426
813 5526535612693698204711534071
814 5773344034656890025459910251
815 6031017761141360066344855271
816 6300028320591819107218595722
817 6580867414347243187588390370
818 6874047767454050618440789504
819 7180104014856061721644621510
820 7499593624411460704445564323
821 7833097858245594863157577154
822 8181222774009392751183583315
823 8544600267676562039269433220
824 8923889159578624444020312722
825 9319776325445368961060213588
826 9732977874289547707680136921
827 10164240375048718884321397615
828 10614342133974158332219990720
829 11084094524836841718412765554
830 11574343374103751420436562721
831 12085970403324322072200622426
832 12619894731056823301536589010
833 13177074436758034093968149699
834 13758508189156816898350205861
835 14365236941733308773716723649
836 14998345698030548413811433465
837 15658965349634621377800738576
838 16348274589772979383977506578
839 17067501905598655500362840711
840 17817927652350815659029541718
841 18600886212709654318667037488
842 19417768244796231547797348859
843 20270023022405671271306675659
844 21159160871205383266735954261
845 22086755704778861626515339070
846 23054447664550352348691594960
847 24063945867786516534942982984
848 25117031268038362304888188315
849 26215559632560440430746755990
850 27361464641424832497045414853
851 28556761113235088376698166032
852 29803548362540247671048896398
853 31104013694251711089604650051
854 32460436040576288804953064526
855 33875189746197570101312539072
856 35350748507665130578525342034
857 36889689473187370930258689156
858 38494697509269287185704077634
859 40168569640891583957051970994
860 41914219672192607737909797124
861 43734682994890002788271186085
862 45633121591965153451090304179
863 47612829244430810674089392496
864 49677236949311212760513587465
865 51829918557284970709269386757
866 54074596638774434866815089195
867 56415148587611697161855882190
868 58855612971771284591314434622
869 61400196141033508145329781644
870 64053279101830857016308279467
871 66819424669933354975057637010
872 69703384912047974522220772869
873 72710108887842663072379378005
874 75844750704357867693907930971
875 79112677895238326401093163901
876 82519480137705965035897552927
877 86070978320701725876421227385
878 89773233978150747937774841667
879 93632559101852300639397881026
880 97655526349063986931936014114
881 101848979660439819074669504392
882 106220045304594633110634798689
883 110776143366203849883461046177
884 115524999695208677024295628951
885 120474658335383448774613540031
886 125633494451234852200433726565
887 131010227772943333388438840904
888 136613936579826021633523964015
889 142454072243599176000473220215
890 148540474353547531250464576933
891 154883386446569205807416274517
892 161493472365959201664987847330
893 168381833273723272377850691090
894 175560025342178319515276085330
895 183040078151596895042050878825
896 190834513821693193457461854569
897 198956366905827612599966175262
898 207419205077928007065587786835
899 216237150643289765063338411256
900 225424902905625382176713446790
901 234997761423989016586141819039
902 244971650194504285050314377590
903 255363142793176159718771911193
904 266189488517472078297725559393
905 277468639565815286019745834585
906 289219279295646953097777621455
907 301460851602284907453832164161
908 314213591462438006147241692678
909 327498556687928552471412581193
910 341337660936933027941605982213
911 355753708031876234567592172876
912 370770427635008185943060482500
913 386412512334659416616187870202
914 402705656197211438400699934017
915 419676594841937729845374497997
916 437353147098069742923954556767
917 455764258305725033356078723765
918 474940045324703826184267118431
919 494911843317619430469293911395
920 515712254376380207314016346271
921 537375198063689834868708606964
922 559935963943981943692638420765
923 583431266181058641989161840653
924 607899300282663822629763119243
925 633379802075295553383701990374
926 659914108995751396991312633521
927 687545223789210605093427557851
928 716317880707092188438900633152
929 746278614301492629878956771356
930 777475830916706218526823515329
931 809959882982169740107425619444
932 843783146215156660143661546159
933 879000099845679458365543530454
934 915667409980347899431161909692
935 953844016226381637918291668001
936 993591221701593552460410364591
937 1034972786560951901927585198431
938 1078055025175301137308851993847
939 1122906907102979771221750702302
940 1169600162000425920914096990628
941 1218209388623414287155929742818
942 1268812168076329740317643375964
943 1321489181472860182023082359336
944 1376324332177692815334228560032
945 1433404872805231792513570614245
946 1492821537158029886302045101639
947 1554668677294551373041208500723
948 1619044405923066826448028827204
949 1686050744325932690103755936233
950 1755793776026239107383551260233
951 1828383806416828944787599996356
952 1903935528580009761082547001993
953 1982568195534909822236953553899
954 2064405799158380436929452387455
955 2149577256034631883970135947110
956 2238216600498421158464870410935
957 2330463185146599554915427567711
958 2426461889103189772513069006001
959 2526363334333909594387986155114
960 2630324110317206266920249474474
961 2738507007390427326763535686478
962 2851081259101744839943303331660
963 2968222793910886757887130759225
964 3090114496594627522964730962766
965 3216946479726367268203868533839
966 3348916365613002312441654795704
967 3486229579086677503687863981170
968 3629099651563931954176652977546
969 3777748536800223534823381991006
970 3932406938783864176460885675827
971 4093314652230038696135050876051
972 4260720916152836028427776923409
973 4434884781011116075842723054755
974 4616075489942590983533486958901
975 4804572874619740831014661527076
976 5000667766281135302120745020017
977 5204662422512420960602525929259
978 5416870970372684931017064879468
979 5637619866484148084787404937692
980 5867248374726202823991004685973
981 6106109062198722305209268842505
982 6354568314144360114596570593279
983 6613006868545264248106451047398
984 6881820371136279678459184919752
985 7161419951604344405822429759114
986 7452232821772430014928305505791
987 7754702896596076517030883537303
988 8069291438831360549139804476549
989 8396477728265055652784934777751
990 8736759756430834040669927563415
991 9090654947769663691039610770013
992 9458700908228116439000450238021
993 9841456202325167769425398244720
994 10239501159756284096054904754780
995 10653438712643207565465970616580
996 11083895264578912106264939410601
997 11531521592659770242096289309490
998 11996993783741092015995696215687
999 12481014206197931736206159646117
1000 12984312518520462987343473997753