#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)<> N; if(N==1){ p(1); return 0; } // 0 ken // 1 pa dp[0][0][0] = 0; dp[0][0][1] = 0; dp[0][1][0] = 0; dp[0][1][1] = 0; dp[1][0][0] = 1; dp[1][0][1] = 1; dp[1][1][0] = 0; // pa ken dp[1][1][1] = 0; FOR(i, 2, N){ // ken ken dp[i][0][0] = dp[i-1][1][0]; dp[i][0][0] %= mod; // ken pa dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][0]; dp[i][0][1] %= mod; // pa ken dp[i][1][0] = dp[i-1][0][1]; dp[i][1][0] %= mod; dp[i][1][1] = 0; } ll sum = 0; sum += dp[N-1][0][0]; sum %= mod; sum += dp[N-1][0][1]; sum %= mod; sum += dp[N-1][1][0]; sum %= mod; p(sum); return 0; }