该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一条道路需要铺设地砖，这条道路由 $n×2$ 个方格组成。 存在两种规格的地砖：$1×1$ 规格，覆盖一个方格； $1×2$ 规格，可以竖放或横放。

砖的数量不限。请计算有多少种方法将道路铺满地砖。

下图是一个例子：

（图片示意，实际题目中可能附有图片）

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

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

输入格式

单个正整数 $n$。

输出格式

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

3

22

4

71

数据规模与约定

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

对于 $70$% 的数据，$1≤n≤50000$；

对于 $100$% 的数据，$1≤n≤100000$。