题目描述
有一条道路需要铺设地砖，这条道路由 $n\times 2$ 个方格组成。存在两种规格的地砖，一种是 $1\times1$ 规格的，也就是恰好可以覆盖一个方格，另一种是 $1\times2$ 规格的。两种规格的砖头的数量没有限制。请计算多少种方法，将这条道路铺满地砖。
下图是一个例子：
其中花纹是 $1 \times 1$ 规格的，灰色是 $1\times 2$ 规格的，可以竖放也可以横放。注意，$1\times 2$ 规格的砖不能交错放置，比如以下放置方法是**不允许**的：
由于方案数可能很大，输出它模 $1,000,000,007$ 的余数即可。
输入
单个正整数：表示 $n$。
输出
单个正整数：表示方案数模 $1,000,000,007$ 的余数。
样例输入输出
提示
+ 对于 $30\%$ 的数据，$1\leq n\leq 15$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 100000$。