0 1
1 1
2 1
3 1
4 2
5 3
6 4
7 6
8 10
9 15
10 22
11 34
12 53
13 80
14 121
15 187
16 287
17 436
18 666
19 1023
20 1564
21 2386
22 3652
23 5593
24 8548
25 13065
26 19995
27 30590
28 46767
29 71524
30 109425
31 167361
32 255934
33 391466
34 598795
35 915805
36 1400649
37 2142358
38 3276767
39 5011632
40 7665186
41 11724011
42 17931702
43 27426003
44 41947833
45 64159032
46 98130083
47 150088220
48 229558526
49 351107147
50 537012746
51 821353593
52 1256250912
53 1921419005
54 2938782794
55 4494830163
56 6874785803
57 10514891583
58 16082384104
59 24597797273
60 37622007756
61 57542355036
62 88010266822
63 134610546316
64 205885044688
65 314898430552
66 481632979016
67 736651272694
68 1126698336900
69 1723270141227
70 2635718854489
71 4031297053341
72 6165815329505
73 9430532756798
74 14423874851739
75 22061125284118
76 33742198430403
77 51608245030194
78 78934126448619
79 120728699428827
80 184652944443105
81 282424229747173
82 431964113875468
83 660683382868446
84 1010506471609493
85 1545556246902376
86 2363907781525207
87 3615565599550264
88 5529959632990642
89 8457999917973078
90 12936398698766033
91 19786050238381085
92 30262501426549030
93 46286094573606436
94 70793967774058524
95 108278434797627781
96 165610429973161432
97 253298956219145845
98 387417394129564070
99 592549766161541008
100 906297008600916070
101 1386169254796429887
102 2120127490996384581
103 3242706879088159112
104 4959677164852612687
105 7585760445416534329
106 11602319994360600151
107 17745594554483648652
108 27141651518379371980
109 41512796028487076842
110 63493270958020555054
111 97112115844553859236
112 148531693225169133732
113 227177254871567626059
114 347464598365318233587
115 531442494916208307181
116 812834247665571374816
117 1243219201509843554435
118 1901487280391860892334
119 2908299576696221120714
120 4448205630945822606041
121 6803471517764578225749
122 10405819454707333504172
123 15915562847764886780116
124 24342642293929544693726
125 37231748541864598739169
126 56945465605034742072338
127 87097334398029851200736
128 133214217824774240194318
129 203749379396253559992886
130 311631973540273060188443
131 476636970479973740763930
132 729009924904156045873615
133 1115011011574674801094127
134 1705394554259638487947175
135 2608378352776160528209085
136 3989480096695246626225048
137 6101856897021007114162568
138 9332709197513003030122960
139 14274254941617320579528079
140 21832283619485693824467002
141 33392188243182469214254937
142 51072909050748230845978602
143 78115337033611597962750644
144 119476371980525284689404684
145 182737526377012803073109415
146 279494623019123210991902530
147 427483319082666817636082223
148 653830066997137893871213420
149 1000024415986189534085366688
150 1529524081328149045771303677
151 2339386796926992635715870495
152 3578061079551055991670322724
153 5472596966784372211526429649
154 8370264479838139544533826667
155 12802208510451881241700605776
156 19580808126179536466888079980
157 29948586336587121049476470184
158 45805965605721546100371267449
159 70059616887801664314542539384
160 107155254857294186294143844646
161 163892541147065358279008753451
162 250671468043399154158277222926
163 383398685817240567200213867838
164 586403205094477445643280255411
165 896895924961495485745507984647
166 1371790422057692004653193559192
167 2098135257031085786333580363383
168 3209070048902676135743154132158
169 4908230079187715598936927240796
170 7507072810230720604637701889557
171 11481968299952228926803619910120
172 17561518234036692927022251535245
173 26860109227586561274877187476801
174 41082180828738324208893037039080
175 62834650721068653007375031890096
176 96104764927104441913124213234382
177 146990963357055829776527873272381
178 224820728972426727867498068902769
179 343860323256172025144325170532055
180 525929803938767253511733923125539
181 804402659928300901581389653368832
182 1230323199890496750806489859800614
183 1881763016949386934971724353032468
184 2878131577355952858950551209308012
185 4402064076061213828683220032000171
186 6732898621525416680056425214853868
187 10297879145889216609597930078453010
188 15750469576996837711666416687973480
189 24090134325856044633711539695396584
190 36845540953607606989156960017089739
191 56354766220911604211642617544100548
192 86193867524223334111788263549261212
193 131832377223606252091523898384203544
194 201635872523563505159135737167166185
195 308399392809087556094688710188140613
196 471692781124048996399537106325375634
197 721447852857068904601930914010828394
198 1103444922671381120792087965650382482
199 1687704374678450524630227335741931339
200 2581321457724492767179471061411581134
201 3948096934558464244227836492289961241
202 6038561899381076533939132029630648808
203 9235900338078901528807095218458774450
204 14126187075049938003263505637471760011
205 21605815781335598781906406023265914732
206 33045808688284001730552582457012012632
207 50543126115424144256975051902905118380
208 77305041060331983155552823122812088677
209 118237035036024587755565696441408132233
210 180841976957227805885625632816787726204
211 276595405321473743497515723036567985932
212 423049004065273405987155516863774601482
213 647047840988576159176567375795430903703
214 989651091256037658591163123281246158527
215 1513658218730627010841179789997313797304
216 2315120170506654587445077974379091706792
217 3540945596279682017971847109756726834910
218 5415829327368573728154650348521208300403
219 8283439128238108284735864539542318673157
220 12669410286709446663131058029838812166613
221 19377695004215060102436842640884181866495
222 29637927510350324239772425432412180155357
223 45330817051135774950723422666155553042653
224 69332883475267428569570066174632029537937
225 106043725741196836776420066237999799760756
226 162192472105759304114094793059948675581984
227 248071234992055355301629058300107622295884
228 379421663851058255166374485692491121613923
229 580320402742848787387686832782967004239349
230 887592359438447281470071855180594439203652
231 1357560741979647725571162175838693736341948
232 2076371150074256531964431336808403245949227
233 3175782135960826960111656901385550093353645
234 4857316657827395129121197240752273405302081
235 7429201407504397001231007122347424610080000
236 11362865022259497770980764948837358527034453
237 17379351350424661339364020278325616226448791
238 26581487395108270697799566944139821632622716
239 40656032431212390053738117153109511381421975
240 62182862398888008564862345812368087570862716
241 95107863332736236497095306000062277845291212
242 145466215589975656835540335236000290880748346
243 222488647484795674619051145110949936679225342
244 340293435550301721360556710899159335748452629
245 520474296498839618123051535606892844801932128
246 796058533653138600792478727891785375799120637
247 1217560969417436040272640697135622098465053601
248 1862243354701184518964748523324701329628202486
249 2848276512828778488968160199580079388444197929
250 4356401150822646838071380713761160535848752390
251 6663057782982090891260126532225230646502624156
252 10191058509608228841992445793791707560163434006
253 15587088830524321055762114203148889814882903170
254 23840245640979640228307644905692411815173278183
255 36463339524262545714147046525764747867660029578
256 55770194203712592611718234227810902789708332686
257 85299772376861643053726949392585268441570938353
258 130464870553741871022114626016047322613098221906
259 199544289208698401284892156688948737366061049459
260 305200343868831968273882633964740397930731610998
261 466799878197631057775595857660470069798365891394
262 713964222723721678288521459978543001770340212216
263 1091998809634811375536715092183895307290588828354
264 1670197696594223363480643179651257974472312167028
265 2554545225778716973761138250517621594938953329965
266 3907143042919824743273097466975518612860554908143
267 5975923465274815958530127991027183847766816220362
268 9140095683861803780218270151763815299051041786934
269 13979655127043589435999543403264876988150209496850
270 21381697110254342322819943219108764757569326721824
271 32703022153261262410433080498342306202767850680374
272 50018838656347189673230543949573166353774459540752
273 76503150345088063560898458693854224384773588977039
274 117010553822213937384656298813620531021027720940668
275 178966090207032823600044482857039121927147453174449
276 273726261416184083507403972973491301724285631276000
277 418660686514437697365903228743211968052444766614875
278 640335967495068502261180984754048498124507027127800
279 979385369764603765644349000336077031491723441580393
280 1497956933859625517795947427820306432005443132489532
281 2291105263536301394434880558109257617987905757252779
282 3504215114568605779566950819937388584781926228480980
283 5359650542733129267794970707639500926783591699166947
284 8197514422214883763830891892098265060326711448090124
285 12537989588431837066509425550084808406013974745242066
286 19176688789179465742032849190939883194187455784136435
287 29330491170318190777976199006965102001316993523924920
288 44860597246461494533191640092145419918911304247436968
289 68613688520354784851548279868598630966775198054878256
290 104943726596052172160035042510570339671169232971664967
291 160510038002108001218540183394129953192407775399470389
292 245497974343969394061506780873141658658595612965316543
293 375485895817934639779981720904743263577169409113282525
294 574300697734699037470224362035873577676485571980966180
295 878385300465415308940779600812545380801524229202969396
296 1343478667389925608884525010340215959594928616298115884
297 2054832803754183636130784859392907995474853264907309284
298 3142839520918723859247491968028836483015332574445896666
299 4806931365025188733546857852170941702821507707600611841
300 7352137770403351637094869431102771782725591380383120990
301 11244997211377558180097541059967454085518264900202327890
302 17199074096914234673272505944187066596639694536377376986
303 26305755726808978728525157265325543201242727814040394897
304 40234304501467145983893598649467203322946086130436458119
305 61537835123551038440581226947286321893195303560230860184
306 94121302669846378463538492068715877692420454207055177402
307 143957284140443989685410706452002112981978595814011398720
308 220180756845089585120186416467738376003482623643470182658
309 336763547425499136341758705201180675407873164918153699814
310 515075379427444455113336109830192812013277921206637601989
311 787800961596111356590078117562061861374456414308891650883
312 1204931122473079019818762251075873338047732539475681847993
313 1842926171304384753653469001617061615590694016937829291631
314 2818731137019428679659919432020171150945930605146623459446
315 4311211890370715262048556500885685354908135524347393697019
316 6593941408447897886868527797484675342152794541662254500424
317 10085345931420934091444001743575143521029405095506252237119
318 15425402844210377805632977894847640415401440851454402979426
319 23592949069288849617916926884106642749353484263883365615744
320 36085102697656723232591519175700547929158078476418322990221
321 55191685993822310784774164330387926003376961865340759938753
322 84414951742356809989992771533804138834549084362615020414775
323 129111549128287910163636943514709843669289763495208556824072
324 197474402037025828090215703904415889965109571357901474135227
325 302034478891842111105906326467740624778969227683577910316261
326 461957729702922459200744668537161490190473739233087895626834
327 706558220820538216995280806376876945324226675322952544764675
328 1080671427946725028248871164580361166350794376744669491619853
329 1652872616532815306734062674098035286717493466730702857829288
330 2528046745600381261318986981835702000307887921423060298178936
331 3866613968925774558514422444022673786404913259966161135700792
332 5913934784121768712844587195829701274217503223777509162254290
333 9045284818169233011425882699627385953724882565643876250789572
334 13834643165405286283762811831743377053962585509890964824038895
335 21159903238164041780397184142364014276979219521236033369661244
336 32363791367462313605153289244747185908314938905868345981405333
337 49499989668549546907949616757817978826956057119362794727712672
338 75709577699537588140223610216221848916131567959890878819545644
339 115796794985680187841591397910908453522397814481494938003499973
340 177109662164151074145791376791990012694545448351806600181901523
341 270886879345656982761474330671747614154782485735978049653575301
342 414317889295152045874762206066445595913699786572079681381972539
343 633693716744948758200564786526320996748543391264102188104336596
344 969226135335803164952648085907139683119655346224288780544867537
345 1482418519538626444616012940506232282772634586303974064734284919
346 2267339464912090123936253384168894520186842077649227936363467448
347 3467865640769129532028624944059230002308847524625238677273959873
348 5304054504645321880988378293998013308658534498835457141793007028
349 8112481019307536420360753159839869466691629352772989350425329171
350 12407932126448965881089300691642281757251189003297293152748576652
351 18977767625976617587074343649884494400764489740128393878591257115
352 29026243889411036476474163819688690974048367585413363691235062805
353 44395255065423657671562065281279792184348597844898423375766385442
354 67901953826104115636002608171058161096873768125683123209427725164
355 103855137820647552633313953040291870205465186825492393407947078668
356 158845055907642940028878194360285879738274448223655526070623441992
357 242951406312474791527732740555632174618029744349985893847950840619
358 371590953787874039868087831120644370737217798115786508393101406155
359 568343435556775266063174159549699327592850241929532285576160950034
360 869273746973059758550770682421396259193882834313375745406968373886
361 1329542667166247196094705886574820329590462164360412193727352111989
362 2033517876239648857771052402500175509975408815823986914426763941113
363 3110238621976577302614085168185357488070184169042928419934824370753
364 4757068722465822298107515295186649712212469154712458996157993653288
365 7275873519917029451821603536400837863745128888138012021113026203432
366 11128352051720893647468861685172890879741472938206697875938227353234
367 17020666872237333403095914145747711904215576690719661141529485159582
368 26032884242809121486114485284215438573710896768732344731814336691125
369 39816951185674410161284865527167239883089202768463504589035725072940
370 60899498762235679449245344750689937229604579380820637051840858715897
371 93144975671213665658611598436999269646005177539674180344524861828944
372 142464004944668641756736748695916324221248293163307699895056173768872
373 217896806119914222287998324164413573201044752299085518781816436560715
374 333270275082465813437267334791814771457999696754213580132611883897532
375 509732465708644951184269476273400390179669257262333405362116919936807
376 779629045924129169949670435548776121284756443598285748382981388075906
377 1192432285833622136109987062756317238610151359037543095559486553408524
378 1823809366431392620736281626665018819001193817759158598584962882727883
379 2789492237504702652980780785610040645793298477695388940497675480312192
380 4266491381346738591029465459819449349288258081108441182417458626002615
381 6525541983005899732975052381807518972748349084026422963922211427036070
382 9980729917361543117211525835418283947934051655253610051735327055946039
383 15265394038186773175653244728701171584492207766446549299511832158788738
384 23348217722608362439211809593248419788474968026337998535190598166792181
385 35710789348682609428351608190631983714440086400785825090672538674118757
386 54619178690934217224357844712058113014388270109402937154572525213559628
387 83539309415524201223288164342516472813330866587871667903529433274503760
388 127772265802690403052875995682964905574551046580815418936828694803978546
389 195425985952902013070475628875778355052748417265038615743818759110747845
390 298901453658495657280200671151748384545939665758041519176863928146647120
391 457165809160576097840799913897172810830315468839724510314250433666969691
392 699229041904339611351726967105344873597016858619857119994282795466156149
393 1069461545998359554351943964018878987029117949880285883863331487476747292
394 1635727250764958406079694576763878799230199292743034304976562067918136954
395 2501823136050553448644656157874248621174743287276857803259079412856857001
396 3826505305912528308850874213186409592951259010383348869845368945258096257
397 5852589115988118870797918077396412643794816338779665752961330329559597006
398 8951457432361806802352948523322217087992253559140513437293519321066765133
399 13691135423207812484466601163929155810841905419708243370213249916267521615
400 20940410049758630619361371177367034503642499937878736732482204339720725386
401 32028079446846358180920068716663013507083216253790509993470977654005159600
402 48986522738379994984208975104170469105762226312205707498332978941734371938
403 74924236839749206038427774163484779636104607531628788960320597754646569214
404 114595626556294687167240579883566008377437890155148222704690137390179763670
405 175272490982021051235574976144309780315244978032321159300670166141812268429
406 268076950388253627379613298807104721079662050019550745421458053981231474164
407 410020140221764336954033447116403744567848720054804558631134877491290630872
408 627120366536524426689952599508621010625113842167117759284234820548524588490
409 959172283371725448678516061927703181704483833625735216034492743290513085797
410 1467041286299775661554651579796711502718243237209545226486483933634033196514
411 2243820190615344619019539224409290052695629707437449914360955766391938185765
412 3431893222658958896606632142298012202824689338556959680921387190804631133660
413 5249035168233569054523561265070193958783835591503191842603283285785052729289
414 8028329673965151507620408308850526626816841546858541888590258822688435670335
415 12279223759813329035254786907950807368310530159068179575526420686230912377461
416 18780909886214853874956021985022013676433646783351912657319730889514991846151
417 28725152587290663353005229906366237490324354393578397519170979450460704110924
418 43934739912083721809240400772472045322734135417048338747911580751923581050177
419 67197602006698453721905976645125684638219614014206682703204901865195508432594
420 102777841054402263913920615198801128892719976531448726720671227776854968616118
421 157197344791425686958854352946220913226355085122486819896115757275180518085230
422 240431254013152154256586422891106519112054300568708177935867001479980225059315
423 367736414269829200156922349752111849498746765402206817703336658675345642132855
424 562447968485137288126348735781929444126985707407549792039552879984624986154873
425 860256708276204620103120274618684428383539474068111244979427326683218541584297
426 1315751226068774839739427944485392446783955828312449630525288233161431051827758
427 2012424049991416533308426963226054487605869496868401623813253149490310677090392
428 3077975894488862936107793319485938099521609950515448101689390832925877511966856
429 4707723308660977535063606761798036170045557601298280790559024793447242111061112
430 7200400363950950649365567637121595830862958884044844285004087104815151410103600
431 11012916860640972048239000031241066008750474082223794532547071033135974169270717
432 16844110278451232524445175326695118329122050740113605803957740451016920670853959
433 25762843274212568210364294255316777082143905355072588335246906926031848308517658
434 39403927105651037257618252907964300720528974754144652757507885266639722631444696
435 60267783909612643453477889120870931991815697776735967574425441486792858492302364
436 92178776182307446920650702373491673973368502170456224446644607706779220477429063
437 140986215640702867060089172208179323739733095467260291350195083179903224032376987
438 215636546978825379509333626988817059506665905437012873610039837425613621552260362
439 329813238703080845710521526279361511130213883092585781550453513218367648127039144
440 504444974415662554572111881982438953956132883509344364296332296146831892661799097
441 771541898117388844807695963062123545371845961367586734137731779110854086545840111
442 1180063100519810482539059341517959280969329756873342197667312350642893277158182293
443 1804890861541461337340049607951393754540028767668641685962486796455395301236652514
444 2760556635184095056765626432191424999094278712166531045468066503321135127481367182
445 4222234761358657023769533464697908236742653050037763271306517558209941344810890415
446 6457852069691928919200650979809825279477235561475586282266949380112245170334039093
447 9877199092691995185020086061754099324631195004947415536975068354641384833219728065
448 15107045014942501861337022505521272144005474007890298530631975680674793092936427520
449 23106024991675832289448927726429678839530339779620256070799246485432262705773069831
450 35340358778826353452180033785351870444020563047407908392744877641464473902660205579
451 54052610047211145121917286290482134529241736290781334873733781181805603788365662616
452 82672750189122438217191559835070873864712827613910053731634854736174778014303607079
453 126446874958736356673953629386968558628090337168083477661015395198193265586642142490
454 193398818235201459360570447990759871012732848548428391274581618516886824895507063961
455 295800927519785020297485016816164049111896281191228301423847099529316583683554435366
456 452423595552452761301275666507660439563664811918187276584962874432336866964063045513
457 691975889084791990604867976600618980997773886576975576848519819100176569067130319857
458 1058367944956518135401340057134431765788237479973439989495361433001269374950183311854
459 1618759735101443023532177714605030803087982345611955616313568152683046493339623530392
460 2475871545876561388216329370051227812546935785850652904626158383113476810972544011959
461 3786812692926938965225027369054777874583999269617235506313355513690308150075333280534
462 5791879790853865623894154224631410212635769341207083836506185718362033188448395697956
463 8858603324732395716386607701339522307668783798507065685124321122649695204735592892982
464 13549116297075414714650212094502326255327327774894993821605716021457415113106438460454
465 20723193679881835445712728261653443103911258257419223880360402561100862326686730558706
466 31695849889973389977151042683981008938519902217696854971469803794746205795774544951782
467 48478382037370148437778562982256182707522548001796500737549525093926652018161178501569
468 74147042376820952271837712868103797185359012186878996158350782915827977319797629954802
469 113406917932864358677065789549288391144962482993104904575836490050364094103329953004930
470 173454376907850055321128738526509102456256310260330110914106387535414138224565789390174
471 265296169024726824573153834912910934072351435009989525351504107174870116357881432764052
472 405766972006637968467764602599692384547407350652652024120369797643031733405852626457518
473 620615202159552773261513033648637258627814804500958798786101201986359278937695184588337
474 949222720732533269738516388457785954656960532772961795095447374281177952292043168628229
475 1451823562200189821461273792794863883496294888288121118889768594406356547315038128953453
476 2220544883431599108077496364798624414929849298358292815480603810164984573098078190415489
477 3396293949012483785409980268407300526702541065309077330189763256903857310676101148219132
478 5194586551330173175478100099325304573181620064205435345304831463804159989422747007211369
479 7945051236541574617421236193542110045793314599331671526616969787467503725015284063180203
480 12151850494262481448781077179306492152245121597192747077492436373940506540689518485855453
481 18586094165855365145302008714971544588419107510245699604370610797813834340180198961135191
482 28427184526763585519674169752450503083272549972313066340384116062613043877871288568917230
483 43479001715338430547280872120661085690434706905645234094722797985742555173165922033412223
484 66500556479049441406461461903371347179519817384359134501420061521654341832506503566912362
485 101711719164498353679481810132507895820429028536739521754893769260256689512432316768713771
486 155566725500364669514910963168658897318754141940204086638444404293979283984451453898387909
487 237937243433723957715896949348198704442771595388371595823033091495671614180379930905667306
488 363921858165655761807314638563725927348724565300716465695989425752010078089182097931621835
489 556613655514731637407122088976752475618983732045935341237819220352112811986854897573525145
490 851333203966122009886816523334877975826483536464259658454185193843766326494382563147982320
491 1302102844575362009406913683136341149947642532576550138496577772582267577290260947805912967
492 1991549031510251105261788869677853461615779965237479811588445636373419231958391968820866830
493 3046047830578917735019161940384504730539322769055866757405160377187543523708147425282626262
494 4658889758359821909323850644952002882576334822947886488925755282587913798840507199898669279
495 7125710096425124037139511994946841925723527028034826885793459132049499945218760162693747924
496 10898679087047280800879181397936151460871654554801404382567045232818080125123967458275428430
497 16669385118829453123203406492634907129990635880030963934740651967213848886512513414860314266
498 25495603459880767885776887719156684552557338177276296203019936968327465851555085593909775250
499 38995187353925018498786077164243102039504752319740027379234420051494841935597025082649712642
500 59642621880299082822523673632576391859496116448739249233564300433156956526798817478114382536