OX 또는
XO 또는
XX 또는
O : 사자, X : 빈자리
n=1, 답:3 n=2, 답:7 이다.
편의상 OX 케이스를 0, XO를 1, XX를 2로 두자
dp[N][C]=A , N:우리의 크기, C:케이스, A:우리의 크기가 N일때 케이스 C에 대한 경우의 수
예를들어, dp[3][1] = dp[2][0] + dp[2][2] 이다.
dp[i][0] = dp[i - 1][1] + dp[i - 1][2]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]
#define MAX 100000+1
#define Modular 9901
int N;
int dp[MAX][3];
int answer;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ifstream cin; cin.open("input.txt");
cin >> N;
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 1;
for (int i = 2; i <= N; i++)
{
dp[i][0] = dp[i - 1][1] + dp[i - 1][2] % Modular;
dp[i][1] = dp[i - 1][0] + dp[i - 1][2] % Modular;
dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] % Modular;
}
for (int i = 0; i < 3; i++)
{
answer += dp[N][i];
answer %= Modular;
}
cout << answer;
}