T3 天花板人物

时间：1s

空间：256M

题目描述

某一天，校长花高价把毕业多年的小 Z 请回来，想见识一下这位能触及学校天花板的人物将会如何改变校园。

现已知学校的天花板可近似看成 $3\times n$的长方形，小 Z 的粉刷工具每次可以粉刷 $1*3$ 的区域，可以竖着或者横着粉刷。由于材料有限，粉刷过的区域不会重复粉刷。请你帮校长算一下小 Z 最后粉刷出来的天花板可能有几种不一样的方案。由于方案数可能很大，输出它模 $10^9+7$ 的余数即可。

• 注意：小 Z 在粉刷的时候必须完全刷满整个天花板，并且每一个小方格不能被重复刷 $2$ 次。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示方案数模 $10^9+7$ 的余数。

样例

3

2

5

4

8

13

说明/提示

样例 1 解释

天花板是 $3*3$ 的矩阵，此时只能竖着刷满整个天花板或者横着刷满整个天花板，共 $2$ 种方案。

样例 2 解释

如下图，竖着刷的 $3\times 1$ 看成是橙色，横着刷的 $1\times 3$ 看成是绿色。

数据范围

对于 $30\%$ 的数据，$1≤n≤15$

对于 $70\%$ 的数据，$1≤n≤300$

对于 $100\%$ 的数据，$1≤n≤200000$