바닥공사

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

태일이는 이 얇은 바닥을 1x2, 2x1의 덮개, 2x2의 텁개를 이용해 채우고자 한다

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오 

예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다

 

입력조건 

→ 첫째 줄에 N이 주어진다 (1 <=N <=1,000)

출력조건

→ 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다

 

POINT

→ 백준 2xn 타일링(2)와 비슷한 문제인 듯

→ 점화식 : dp[i] = dp[i-1]+ dp[i-2]*2

n = int(input())
arr = [0,1,3]
for i in range(3, n+1):
    arr.append(arr[i-1]+arr[i-2]*2)
print(arr[n] %796796)