> 문제 <

https://www.acmicpc.net/problem/1309

> 풀이 <

> 코드 <

n = int(input())
dp = [[0] * 3 for _ in range(n+1)]

dp[1][0], dp[1][1], dp[1][2] = 1, 1, 1

if n >= 2:
    for i in range(2, n+1):
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%9901
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%9901
        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%9901


print(sum(dp[n])%9901)