[python] 바닥 공사

- 가로 길이 N, 세로 길이 2인 직사각형 형태의 얇은 바닥

-  1 x 2, 2 x 1, 2 x 2 의 덮개를 이용해 채움

- 바닥을 채우는 모든 경우의 수

 

n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3, n+1):
    d[i] = (d[i-1] + 2*d[i-2]) % 796796

print(d[n])