package Practice;

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class B10844_2 { //쉬운 계단 수, 일의 자릿수부터 시작(Bottom-Up)

public static void main(String[] args) throws Exception {

// TODO Auto-generated method stub

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine()), mod = 1000000000;

int[][] dp = new int[N + 1][10];

//가장 큰 자릿수, 즉 가장 앞에 있는 숫자

for(int i = 1; i < 10; i++) dp[1][i] = 1;

//십의 자릿수에서 시작해서 가장 큰 자릿수가 되면 반복문을 종료한다.

//뒤의 자릿값에 0이 들어가려면, 앞의 자리 숫자가 1이여야 한다.

//뒤의 자릿값에 9가 들어가려면, 앞의 자리 숫자가 8이여야 한다.

//뒤의 자릿값에 1~8까지가 들어가려면, 앞의 자리 숫자는 (뒤의 자릿값 - 1)과 (뒤의 자릿값 + 1)이다.

//여기서 i는 자릿수를 의미하고, j는 뒤의 자릿값를 의미한다.

//i - 1은 앞의 자릿수이다.

for(int i = 2; i <= N; i++) {

for(int j = 0; j < 10; j++) {

if(j == 0) dp[i][j] = dp[i - 1][1];

else if(j == 9) dp[i][j] = dp[i - 1][8];

else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;

}

}

//res를 마지막 자릿값의 0~9를 모두 더해준다.

long res = 0;

for(int i = 0; i < 10; i++) res += dp[N][i];

System.out.println(res % mod);

}

}