三扔硬币

题目描述

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

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

输入描述

单个整数：表示n。

数据范围

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

输出描述

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