题目描述

扔一枚硬币有两种结果：正面与反面。给定 $n$，请统计有多少种扔硬币的结果中不含三个连续的正面硬币且不含三个连续的反面硬币。

当 $n$ 较大的时候，答案可能很大，所以输出答案模 $1,000,000,007$ 的余数即可。

输入格式

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

输出格式

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

3

6

样例解释 1

正正反 正反正 正反反 反正正 反正反 反反正

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 1,000,000$。