再铺地砖(Tile Again)

题目描述

有一条道路需要铺设地砖，这条道路由 $n\times 2$ 个方格组成。存在两种规格的地砖，一种是 $1\times 1$ 规格的，也就是恰好可以覆盖一个方格，另一种是 $1\times 2$ 规格的。两种规格的砖头的数量没有限制。请计算有多少种方法，将这条道路铺满地砖。

下图是一个例子：

其中花纹是 $1\times 1$ 规格的，灰色是 $1\times 2$ 规格的，可以竖放也可以横放。注意，如果上下两行都放置 $1\times 2$ 规格的砖，它们可以不对齐，例如以下放置方法是允许的：

本题可以用暴力枚举所有可能的放置方式，时间复杂度完全可以接受。

由于方案数可能很大，输出它模 $1,000,000,007$ 的余数即可。

注意：当n=1时不需要特殊判断，直接使用递推公式即可，无需单独处理边界。

输入格式

单个正整数：表示 $n$。

输出格式

单个自然数：表示方案数模 $1,000,000,007$ 的余数。

样例输入 #1

3

样例输出 #1

22

样例输入 #2

4

样例输出 #2

71

对于大规模数据，可以考虑使用矩阵快速幂来加速递推计算。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 15$；
• 对于 $70\%$ 的数据，$1\leq n\leq 50000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$。

知识点与难度

本题涉及的知识点从属于 GESP五级（递推算法、矩阵快速幂），难度等级：普及/提高-。