四铺地砖(Tiling)

题目描述

有一条道路需要铺设地砖，这条道路由 $n\times 2$ 个方格组成。存在两种规格的地砖：一种是 $1\times 2$ 的（恰好覆盖两个方格），另一种是 $2\times 2$ 的。两种规格的地砖数量没有限制。请计算有多少种方法将这条道路铺满地砖，答案对 $1,000,000,007$ 取模。

输入格式

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

输出格式

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

样例输入 #1

2

样例输出 #1

3

样例输入 #2

8

样例输出 #2

171

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布