#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); #define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i) #define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i) #define VFOR(i, s, n) for(int i = (s); i < (n); ++i) #define VFORS(i, s, n) for(int i = (s); i <= (n); ++i) #define REP(i, n) FOR(i, 0, n) #define REPS(i, n) FORS(i, 0, n) #define VREP(i, n) VFOR(i, 0, n) #define VREPS(i, n) VFORS(i, 0, n) #define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i) #define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i) #define RREP(i, n) RFOR(i, n, 0) #define RREPS(i, n) RFORS(i, n, 0) #define ALL(v) (v).begin(), (v).end() #define SORT(v) sort(ALL(v)) #define RSORT(v) sort(ALL(v), greater()) #define SZ(x) ((int)(x).size()) #define PB push_back #define MP make_pair #define MT make_tuple #define BIT(n) (1LL<<(n)) #define UNIQUE(v) v.erase(unique(ALL(v)), v.end()) using ll = long long; using PII = pair; using VI = vector; using VD = vector; using VLL = vector; using VS = vector; using VC = vector; using VB = vector; const int MOD = 1000000007; const int INF = 1000000000; template bool chmax(T &a, const T &b){ if(a < b){ a = b; return true; } return false; } template bool chmin(T &a, const T &b){ if(b < a){ a = b; return true; } return false; } int main(){ int n; cin >> n; //dp[i][j] = i段目へ最後に(j+1)段登ってきた時の場合数 vector dp(n+4, VI(3, 0)); dp[1][0] = dp[2][1] = dp[3][2] = 1; FOR(i, 1, n){ dp[i+1][0] = (dp[i][1] + dp[i][2]) % MOD; dp[i+2][1] = (dp[i][0] + dp[i][2]) % MOD; dp[i+3][2] = (dp[i][0] + dp[i][1]) % MOD; } cout << ((dp[n][0] + dp[n][1]) % MOD + dp[n][2]) % MOD << "\n"; return 0; }