#include using namespace std; #define rep(i,a,b) for(int i=a;i> n; int dp1[n+1]; int dp2[n+1]; int dp3[n+1]; rep(i,0,n+1){ dp1[i] = 0; dp2[i] = 0; dp3[i] = 0; } dp1[1] = 1; dp2[2] = 1; dp1[3] = 1; dp2[3] = 1; dp3[3] = 1; rep(i,4,n+1){ dp1[i] = (dp2[i-1] + dp3[i-1]) % mod; dp2[i] = (dp1[i-2] + dp3[i-2]) % mod; dp3[i] = (dp1[i-3] + dp2[i-3]) % mod; } cout << (dp1[n] + dp2[n] + dp3[n])%mod << endl; }