package Baekjoon;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Number1309 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //입력
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //출력
final int MOD = 9901;
int N = Integer.parseInt(br.readLine());
/*dp[i][j] : i번째 줄의 j번쨰 칸에 동물을 놓을 수 있는 경우의 수
* j = 0 : 어느칸에도 동물을 놓치 않는 경우의수
* j = 1 : 첫번째 칸에 동물을 놓는 경우의 수
* j = 2 : 두 번째 칸에 동물을 놓는 경우의 수
* */
long[][] dp = new long[N + 1][3];
dp[1][0] = dp[1][1] = dp[1][2] = 1; //첫번째 줄에 동물을 배치하는 경우의 수
for (int i = 2; i <= N; i++) { //두번째 줄 부터 동물을 배치하는 경우의 수
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
/*
* 두번쨰 줄에 동물을 놓지 않는 경우의 수
* dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2] = 3
*
* 두 번째 줄의 첫 번째 칸에 동물을 놓는 경우
* dp[2][1] = dp[1][0] + dp[1][2] = 2
*
* 두 번째 줄의 두 번째 칸에 동물을 놓는 경우
* dp[2][2] = dp[1][0] + dp[1][1] = 2
*
* 즉 점화식으로
* N줄에 동물을 배치하는 경우의 수는
* dp[N][0]+dp[N][1]+dp[N][2]이다
*
* */
}
long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
bw.write(ans + "\n");
bw.flush();
bw.close();
br.close();
}
}
JAVA