暂无测试数据。

小 Y 得到了一个新的拼图玩具，玩具由一个 $4\times n$ 的木板，无数块 $1\times 4$ 的拼图和无数块 $2\times 2$ 的拼图组成。

显然要把这个木板拼完很简单，但是小 Y 想知道，拼完这个木板一共有多少种不同的方案。

方案数对 $10^9+7$ 取模。

输入格式

共一行，一个正整数 $n$。

输出格式

共一行，一个整数 $ans$，表示方案数对 $10^9+7$ 取模的结果。

数据范围

对于 $20\%$ 的数据， $4\le n \le 10$

对于 $50\%$ 的数据， $4\le n \le 10^6$

对于 $100\%$ 的数据， $4\le n \le 10^{18}$

4

9