6497: 三扔硬币
[Creator : ]
Description
扔 $n$ 次硬币的结果可以用一串 $0/1$ 序列来表示。
给定 $n$，请统计有多少种扔硬币的结果中不含三个连续的 $0$ 且不含三个连续的 $1$。
当 $n$ 较大的时候，答案可能很大，所以输出答案模 $1,000,000,007$ 的余数即可。
给定 $n$，请统计有多少种扔硬币的结果中不含三个连续的 $0$ 且不含三个连续的 $1$。
当 $n$ 较大的时候，答案可能很大，所以输出答案模 $1,000,000,007$ 的余数即可。
Input
单个整数：表示 $n$。
Output
单个整数：表示答案模 $1,000,000,007$ 的余数。
Constraints
对于 $30\%$ 的数据，$1≤n≤20$；
对于 $60\%$ 的数据，$1≤n≤5000$；
对于 $100\%$ 的数据，$1≤n≤1,000,000$。
对于 $60\%$ 的数据，$1≤n≤5000$；
对于 $100\%$ 的数据，$1≤n≤1,000,000$。
Sample 1 Input
3
Sample 1 Output
6
Sample 2 Input
1
Sample 2 Output
2
Sample 3 Input
4
Sample 3 Output
10
108
85675462
Sample 4 Input
1000000
Sample 4 Output
68801319
HINT
题目来源：IAI 2022年3月赛 丙组T4。