백준 1309 동물원

n = int(input())

g = [[1] * 3 for _ in range(n)]
mod = 9901
for i in range(1, n):
    g[i][0] = (g[i-1][0] + g[i-1][1] + g[i-1][2]) % mod
    g[i][1] = (g[i-1][0] + g[i-1][2]) % mod
    g[i][2] = (g[i-1][0] + g[i-1][1]) % mod
    
print(sum(g[n-1]) % mod)

dp + 이차원 리스트