再铺地砖(Tiling Again)

题目描述

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

其中花纹是 1 × 1 规格的，灰色是 1 × 2 规格的，可以竖放也可以横放。注意，如果上下两行都放置 1 × 2 规格的砖，它们可以不对齐。

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

输入格式

单个正整数：表示 n。

输出格式

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

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 15
• 对于 70% 的数据，1 ≤ n ≤ 50000
• 对于 100% 的数据，1 ≤ n ≤ 100000

样例输入 #1

3

样例输出 #1

22

样例输入 #2

4

样例输出 #2

71

知识点与难度

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

测试点分布