3136: 三扔硬币
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：24
题目描述
扔一枚硬币有两种结果：正面与反面。给定 �n，请统计有多少种扔硬币的结果中不含三个连续的正面硬币且不含三个连续的反面硬币。
当 �n 较大的时候，答案可能很大，所以输出答案模 1,000,000,0071,000,000,007 的余数即可。
输入
- 单个整数：表示 �n。
- 对于 30%30% 的数据，1≤�≤201≤n≤20；
- 对于 60%60% 的数据，1≤�≤50001≤n≤5000；
- 对于 100%100% 的数据，1≤�≤1,000,0001≤n≤1,000,000。
输出
- 单个整数：表示答案模 1,000,000,0071,000,000,007 的余数。
样例输入 复制
3样例输出 复制
6提示
正正反
正反正
正反反
反正正
反正反
反反正
正反正
正反反
反正正
反正反
反反正