[10844] 쉬운 계단수

n = int(input())
dp = [[0]*10 for _ in range(n+1)]
for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[n]) % 1000000000)

n	f(n)
1	9	1,2,3,4,5,6,7,8,9
2	17	12,23,34,45,56,67,78,89, 10,21,32,43,54,65,76,87,98

dp[자리수][앞의 숫자] = 경우의 수

dp[2][0] = 0 (X)

dp[2][1] ~dp[2][8] = 2 → dp[n][i] = dp[n-1][i-1]+dp[n-1][i+1]

dp[2][9] = 1 → dp[n][9] = dp[n-1][8]