#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define pb push_back #define mp make_pair #define YES cout<<"YES"<> n; ll dp[1000005][3] = {}; dp[1][1] = 1; dp[1][0] = dp[1][2] = 0; for (int i = 2; i <= n; i++) { dp[i][0] = (dp[i - 1][1] + dp[i - 1][2])%MOD; dp[i][1] = dp[i - 1][0]%MOD; dp[i][2] = dp[i - 1][1]%MOD; } cout << (dp[n][0] + dp[n][1] + dp[n][2])%MOD << endl; return 0; }