#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; #define rep(i,n) for(int i=0;i=0;i--) #define all(x) (x).begin(),(x).end() int main() { int N; cin >> N; //ケン:0、パ:1とすると2歩分のパターンは //00→可 //01→可 //10→可 //11→不可 //よって、ケンケンパのコースの末尾が00、01、10のパターンを使用して //動的計画法で計算すればよい if (N == 1) { cout << 1 << endl; return 0; } //dp[i][j][k] := 長さがkで末尾がijのケンケンパのコースの個数を10^9+7で割った数 vector>> dp(2, vector>(2, vector(N + 1, 0))); //auto dp = new vector>>(2, vector>(2, vector(N, 0))); //初期化 dp[0][0][2] = 1; dp[0][1][2] = 1; dp[1][0][2] = 0; //dp[1][1][2] = 1; reple(i, 3, N) { //ケンは2回まで dp[0][0][i] = dp[1][0][i - 1] % mod; dp[0][1][i] = (dp[0][0][i - 1] + dp[1][0][i - 1]) % mod; dp[1][0][i] = dp[0][1][i - 1] % mod; } cout << (dp[0][0][N] + dp[0][1][N] + dp[1][0][N]) % mod << endl; return 0; }