#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; templateinline bool chmin(T& a,T b){ if(a>b){ a=b; return true; } return false; } templateinline bool chmax(T& a,T b){ if(a>n; rep(i,n){ rep(j,3){ dp[i][j]=0; } } dp[1][1]=1; re(i,1,n){ rep(j,3){ if(j==0){ (dp[i+1][1]+=dp[i][0])%=mod; } else if(j==1){ (dp[i+1][0]+=dp[i][1])%=mod; (dp[i+1][2]+=dp[i][1])%=mod; } else if(j==2){ (dp[i+1][0]+=dp[i][2])%=mod; } } } ll ans=0; rep(i,3){ (ans+=dp[n][i])%=mod; } cout<