문제

입력

첫 줄에 n이 입력된다.

입력 예시

3

출력

2*n 의 직사각형을 채울 수 있는 방법의 수에 100,000,007으로 나눈 나머지를 출력하시오.

출력 예시

3

문제 풀이

이전에 풀었던 공식에 나머지만 구하면 된다.

# 2*n 의 n 값 받기
n = int(input())

# 네모 상자를 채우는 공식 : T(i) = T(i-1) +T(i-2)
def fibo(n):
    cnt = 0
    if n == 1:
        cnt = 1
    elif n == 2:
        cnt = 2

    fib = [1,2]
    for i in range(2,n):
        fib.append(fib[i-1]+fib[i-2])
    cnt = fib[n-1]
    return cnt

result = fibo(n)%100000007
print(result)