1309 동물원

import java.util.Scanner;

public class Zoo1309 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int dp[][] = new int[n][3];

        /*
         * dp[i][0] -> 사자가 칸에 없어도 되는 경우
         * dp[i][1] -> 사자가 첫번 째 칸에 있는 경우
         * dp[i][2] -> 사자가 두번 째 칸에 있는 경우
         */

        dp[0][0] = 1;
        dp[0][1] = 1;
        dp[0][2] = 1;

        for(int i =1; i<n; i++){
            dp[i][0] = dp[i-1][1]+dp[i-1][2]+dp[i-1][0];
            dp[i][1] = dp[i-1][0]+dp[i-1][2];
            dp[i][2] = dp[i-1][0]+dp[i-1][1];
        }

        int result = 0;
        for(int i =0; i<3; i++){
            result += dp[n-1][i];
        }
        System.out.println(result%9901);
    }
}