#include using namespace std; typedef long long ll; #define rep(i,n) for(i=0;i=0) return dp[x][y]; long ret=0; if(x==n) ret=1; else{ if(y==0){//ケンしか置けない ret=rec(x+1,y+1); } else if(y==1){//両方おける long a=rec(x+1,y+1)%mod; long b=rec(x+1,0)%mod; ret=a+b; } else if(y==2){//パしか置けない ret=rec(x+1,0); } } return dp[x][y]=ret%mod; } int main(int argc, char const *argv[]) { cin >>n; memset(dp,-1,sizeof(dp)); std::cout << rec(0,0) << std::endl; return 0; }