#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector vi; typedef vector vvi; #define rep(i,n) for(ll i=0;i<(n);i++) #define tii tuple #define tiii tuple #define mt make_tuple #define pb push_back #define ALL(a) (a).begin(),(a).end() #define FST first #define SEC second const int INF = (INT_MAX/2); const ll LLINF = (LLONG_MAX/2); const double eps = 1e-5; const double PI = M_PI; #define DEB cerr<<"!"<0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;} ll dp[1000001][3] ={}; int main(){ int n; cin >> n; dp[0][1] = 1; rep(i,n){ if(i == 0)continue; rep(j,3){ if(j == 0) dp[i][j] += dp[i-1][1] + dp[i-1][2]; else dp[i][j] += dp[i-1][j-1]; dp[i][j] %= DIV; } } cout << (dp[n-1][0]+dp[n-1][1]+dp[n-1][2])%DIV <