> 문제 <

https://www.acmicpc.net/problem/10844

> 풀이 <

dp[i-1]의 끝자리 +1, -1 해서 다음 계단 수 생성 가능
단, 끝자리가 0일 때는(min) -1로 내려갈 수가 없고 9일 때는(max) 10으로 올라갈 수가 없다.

dp[i]에 0의 갯수는 이전 dp[i-1] 1의 갯수와 동일하다.   (1에서 -1 한게 0이 되니까)
9의 갯수도 이전 dp[i-1] 8의 갯수와 동일하다.   (8 + 1 = 9)

→ dp[N][S] : N은 길이, S는 0~9까지 숫자    => 끝자리에 각 숫자가 몇개 있는지 2차원 리스트로!
끝자리가 1~8 사이의 숫자라면, dp[i][S] = dp[i-1][S-1] + dp[i-1][S+1]
    ex. dp[2][3] = dp[1][2] + dp[1][4] ( 3에서 -1 하면 2, +1 하면 4 )

> 코드 <

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 S in range(10):
        if S == 0:
            dp[i][S] = dp[i-1][S+1]
        elif S == 9:
            dp[i][S] = dp[i-1][S-1]
        else:
            dp[i][S] = dp[i-1][S+1] + dp[i-1][S-1]

print(sum(dp[n])%1000000000)