#include using namespace std; #define rep(i,j,n) for(int i=j;i pi; template using vt = vector; template using vvt = vector>; i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));} i64 lcd(i64 n, i64 m) {return (n / gcd(n, m) * m);} int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int dp[1000100][3]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; dp[1][0] = dp[2][1] = dp[3][2] = 1; rep(i, 0, 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 << endl; }