# 10844 쉬운 계단 수

n = int(input()) # 1<=n<=100   # 0 ~ 9 인데, 0은 맨 처음에 올 수 x 

data = [ [0,0,0,0,0,0,0,0,0,0] for i in range(n+1) ] 

for i in range(1,10):
  data[1][i]=1

if n>1:
  data[2][0]=1
  data[2][1]=1
  for i in range(2,9):
    data[2][i]=2
  data[2][9]=1

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

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