#include #define REP(i,n,N) for(int i=(n);i<(int)N;i++) #define p(s) cout<<(s)<>n; dp[1][0]=1; dp[2][1]=1; dp[3][2]=1; dp[3][1]=1; dp[3][0]=1; REP(i,4,n+1){ dp[i][0]=(dp[i-1][1]+dp[i-1][2])%mod; dp[i][1]=(dp[i-2][0]+dp[i-2][2])%mod; dp[i][2]=(dp[i-3][0]+dp[i-3][1])%mod; } p((dp[n][0]+dp[n][1]+dp[n][2])%mod); return 0; }