题目描述

扔 $n$ 次硬币的结果可以用一串 $0/1$ 序列来表示。给定 $n$，请统计有多少种扔硬币的结果中不含三个连续的 $0$ 且不含三个连续的 $1$。

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

输入格式

单个整数：表示 $n$。

输出格式

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

3

6

数据范围

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