#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)); for (int i = 0; i < min(3,N); i++) { dp[i][i] = 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; } } } } int ans = 0; for (int i = 0; i < 3; i++) { ans += dp[N - 1][i]; ans %= MOD; } cout << ans << endl; getchar(); getchar(); }