"""
DP 기반 풀이 
길이가 N일 때 쉬운 계단 수(인접한 수의 차이가 1)인 값을 찾는 문제.
dp를 2차원으로 만들고, 1일 때는 0을 제외하고 모두 1개씩 있음.
그래서 1만 만들어주고, 그 외 자릿수에 대해서 계싼. 
j가 0일 때와 j가 9일 때는 한개의 경우 수만 더하고, 
나머지는 전의 자리 수의 앞 뒤 값을 더해준다.
"""

n = int(input())
dp = [[0] * 10 for _ in range(n + 1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][j + 1]
        elif j == 9:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

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