Untitled

signed main() {
    fastio;
    int t=1;
    //cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<ull> dp(n+1,0);
        dp[0] = 1;
        if(n>=1){
            dp[1] = 2;
        }
        if(n>=2){
            dp[2] = 4;
        }
        for(int i=3; i<=n;i++){
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD;
        }
        cout << dp[n] << '\n';
    }
}