1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    dp = [0] * (n+1)
    dp[1] = 1
    if n == 1:
        return 1
    dp[2] = 2

    for i in range(3, n+1):
        dp[i] = (dp[i-2] + dp[i-1]) % 1234567

    return dp[n]