PRoblem Description

今年的ACM暑期集訓(xùn)隊(duì)一共有18人，分為6支隊(duì)伍。其中有一個(gè)叫做EOF的隊(duì)伍，由04級(jí)的阿牛、XC以及05級(jí)的COY組成。在共同的集訓(xùn)生活中，大家建立了深厚的友誼，阿牛準(zhǔn)備做點(diǎn)什么來紀(jì)念這段激情燃燒的歲月，想了一想，阿牛從家里拿來了一塊上等的牛肉干，準(zhǔn)備在上面刻下一個(gè)長(zhǎng)度為n的只由”E” “O” “F”三種字符組成的字符串（可以只有其中一種或兩種字符，但絕對(duì)不能有其他字符）,阿牛同時(shí)禁止在串中出現(xiàn)O相鄰的情況，他認(rèn)為，”O(jiān)O”看起來就像發(fā)怒的眼睛，效果不好。

你，NEW ACMer,EOF的崇拜者，能幫阿牛算一下一共有多少種滿足要求的不同的字符串嗎？

PS: 阿牛還有一個(gè)小秘密，就是準(zhǔn)備把這個(gè)刻有 EOF的牛肉干，作為神秘禮物獻(xiàn)給杭電五十周年校慶，可以想象，當(dāng)校長(zhǎng)接過這塊牛肉干的時(shí)候該有多高興！這里，請(qǐng)?jiān)试S我代表杭電的ACMer向阿牛表示感謝！

再次感謝！

Input

輸入數(shù)據(jù)包含多個(gè)測(cè)試實(shí)例,每個(gè)測(cè)試實(shí)例占一行,由一個(gè)整數(shù)n組成，(0 < n < 40)。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出全部的滿足要求的涂法，每個(gè)實(shí)例的輸出占一行。

Sample Input

1 2

Sample Output

3 8

這道題我是先畫出了樹，發(fā)現(xiàn)O的數(shù)目是上一層E+F的數(shù)量，E+F是上一層（E+O+F）*2的數(shù)量 令f[n]等于本層E+F的數(shù)量 所以得到遞推公式： O=f[n-1] E+F=(f[n-1]+f[n-2])*2 E+F+O=f[n]+f[n-1]