问题 A: 三扔硬币

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:28 解决:24

题目描述

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

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

输入

  • 单个整数:表示 n


  • 对于 30%30% 的数据,1≤�≤201n20
  • 对于 60%60% 的数据,1≤�≤50001n5000
  • 对于 100%100% 的数据,1≤�≤1,000,0001n1,000,000



输出

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

样例输入 复制

3

样例输出 复制

6

提示

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