走棋子[1]

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　长度为 \(n(1≤n<50)\) 的只由 'H'、'M'、'Y' 三种字母组成的字符串，可以只有其中一种或两种字母，但绝对不能有其他字母，且禁止出现 'Y' 相邻的情况，问这样的串有多少种？

【输入格式】

　　有若干行，每行包含一个正整数：\(n\)。

【输出格式】

　　输出若干行，每行一个整数，表示对应输入的答案 \(mod\ 10^9+7\)。

【输入输出样例】

　Input

4
7
20

　Output

60
1224
578272256

【数据限制】

　　对于 \(100\%\) 的数据，\(0≤n≤50\)。

【来源】

　　Mr.he