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

题目描述

有一条道路需要铺设地砖，这条道路由 $n×2$ 个方格组成。存在两种规格的地砖，一种是 $1×2$ 规格的，也就是恰好可以覆盖两个方格，另一种是 $2×2$ 规格的。两种规格的砖头的数量没有限制。请计算有多少种方法，将这条道路铺满地砖。 由于方案数可能很大，输出它模 $1,000,000,007$ 的余数即可。

输入格式

单个整数 $n$。

输出格式

输出单个整数，该整数表示方案数模 $1,000,000,007$ 的余数。

数据范围

• 对于 30% 的数据，$1 \leq n \leq 15$；
• 对于 70% 的数据，$1 \leq n \leq 50000$；
• 对于 100% 的数据，$1 \leq n \leq 10^{12}$。

样例输入输出

样例 1

• 输入

2

• 输出

3

样例 2

• 输入

8

• 输出

171