[백준][동적 계획법 1] No.1904_01 타일 完

# ---------- Function ----------
def fibonacci(N):
    fibonacci_list[1] = 1
    fibonacci_list[2] = 1
    
    for i in range(3, N+1):
        fibonacci_list[i] = (fibonacci_list[i-1] + fibonacci_list[i-2]) % 15746	# 메모리 초과 방지
    
    return fibonacci_list[N]

# ---------- Main ----------
N = int(input())
fibonacci_list = [0] * (N+2)

print(fibonacci(N+1))

# ---------- Comment ----------
# N이 1자리일 때부터 6자리일 때까지만이라도 직접 구해보자
# 그럼 자릿수에 따라 피보나치 수가 보임을 알 수 있다.
# 15746으로 나눈 나머지 값을 구하는 걸 빼먹지 말자.
# 재귀 최대 반복 제한을 늘리거나, 반복문으로 처리하자.
# sys.setrecursionlimit(10**6) 파이썬의 최대 재귀 반복 횟수 제한 변경, 기본값(1000)