#include #define rep(i,a,b) for(int i=int(a);i> N; ll dp[N+1][3] = {}; dp[2][0] = dp[1][1] = dp[2][2] = 1; rep(i,2,N){ dp[i+1][0] = (dp[i][1] + dp[i][2]) % MOD; dp[i+1][1] = dp[i][0]; dp[i+1][2] = dp[i][1]; } ll ans = 0; rep(i,0,3)ans += dp[N][i]; cout << ans % MOD<< endl; }