4015: Sky 不想拼图
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：1
题目描述
picture.in/out
Sky 买到了一个新玩具，这个玩具是由一个 4 × n 的木板，无数块 1 × 4 的拼图和无数块 2 × 2 的拼图组成。
Sky 知道这个玩具的玩法就是用这些拼图把木板全部覆盖（不能重叠），但是他不想玩这种无聊的游戏，于是 Sky 想让你计算一下一共有多少种不同方案可以拼完这个木板。
方案数对 10^9 + 7 取模。
输入
共一行，一个正整数 n。
输出
共一行，一个整数 ans，表示方案数对 10^9 + 7 取模的结果。
样例输入 复制
4样例输出 复制
9提示
对于 20% 的数据， 4 ≤ n ≤ 10
对于 50% 的数据， 4 ≤ n ≤ 10^6
对于 100% 的数据， 4 ≤ n ≤ 10^18
大样例下载：
/upload/59.60.22.18:2500/file/20230101/20230101173654_85619.rar：
大样例下载：
/upload/59.60.22.18:2500/file/20230101/20230101173654_85619.rar：