백준
메모리 초과 주의. 15746으로 바로바로 나눠서 넣어줘야 한다.
n = int(input())
dp = []
dp.append(1)
dp.append(2)
for i in range(2, n):
dp.append((dp[i-1] + dp[i-2])%15746)
print(dp[n-1])n이 1일 때 1 1개
n이 2일 때 11, 00 2개
n이 3일 때 111, 001, 100 3개
n이 4일 때 1111, 0000, 0011, 1100, 1001 5개
n이 5일 때 11111, 00001, 10000, 00100, 00111, 10011, 11001, 11100 8개
...
이렇게 만들 수 있는 가짓 수로 피보나치 수열을 이룬다.
