백준 1904번(python)

---

N = int(input())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3, N + 1):
    # int의 범위를 벗어나기 때문에 마지막에도 % 15746을 해줘야함
    # (x % mod + y % mod) % mod는
    # (x + y) % mod 와 다르다.
    dp[i] =  ((dp[i - 2] % 15746) + (dp[i - 1] % 15746)) % 15746

print(dp[N])