#include #include #include #include #include #include #include #include #include #include #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) (obj).rbegin(),(obj).rend() #define P pair #define MOD 1000000007 #define INF 1012345678 #define NINF (-2147483647-1) #define LLINF 9223372036854775807 using ll = long long; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; // dp[i][j] := i+1段目にいて前回j+1stepjumpした vector> dp(N, vector(3, 0)); dp[0][0] = dp[1][1] = dp[2][2] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { if (j != k && i + k + 1 < N) { dp[i + k + 1][k] += dp[i][j]; dp[i + k + 1][k] %= MOD; } } } } cout << (dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]) % MOD << endl; getchar(); getchar(); }