#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; #define MOD 1000000007 // 10^9 + 7 #define INF 1000000000 // 10^9 #define LLINF 1LL<<60 ll dp1[1000009]; // dp1[i] : 最後が1ジャンプでi段目に到達する場合の数 ll dp2[1000009]; ll dp3[1000009]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; dp1[1] = 1; dp2[2] = 1; dp3[3] = 1; for (int i = 1; i < N; i++) { dp1[i + 1] += (dp2[i] + dp3[i]); dp1[i + 1] %= MOD; dp2[i + 2] += (dp1[i] + dp3[i]); dp2[i + 2] %= MOD; dp3[i + 3] += (dp1[i] + dp2[i]); dp3[i + 3] %= MOD; } cout << (dp1[N] + dp2[N] + dp3[N]) % MOD << endl; return 0; }