module main; // https://mmxsrup.hatenablog.com/entry/2016/08/30/001141 より // 動的計画法 import std; void main() { // 入力 auto N = readln.chomp.to!int; // 答えの計算 immutable MOD = 10L ^^ 9 + 7; // dp[i][j] : i番目まででj回連続ケンをしたときの場合の数 auto dp = new long[][](N + 1, 3); dp[1][1] = 1; // ケン foreach (i; 1 .. N) { // * パー dp[i + 1][1] += dp[i][0]; dp[i + 1][1] %= MOD; // * パー ケン dp[i + 1][0] += dp[i][1]; dp[i + 1][0] %= MOD; dp[i + 1][2] += dp[i][1]; dp[i + 1][2] %= MOD; // * パー ケン ケン dp[i + 1][0] += dp[i][2]; dp[i + 1][0] %= MOD; } long ans = 0; foreach (i; 0 .. 3) { ans += dp[N][i]; ans %= MOD; } // 答えの出力 writeln(ans); }