#include #define REP(i,n,N) for(int i=(n);i<(int)N;i++) #define p(s) cout<<(s)<>N; dp[0][0]=1; dp[0][1]=0; dp[0][2]=0; int from=0,to=1; REP(i,0,N){ dp[to][0]=(dp[from][1]+dp[from][2])%mod;//パ dp[to][1]=dp[from][0];//ケン1 dp[to][2]=dp[from][1];//ケン2 swap(from,to); } p((dp[N%2][0]+dp[N%2][1]+dp[N%2][2])%mod); return 0; }