import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine());
//첫번째 자릿수는 1~9
//두번째 부터는 0~9
//인접한 자리 차이 +1 or -1
dp = new Long[k + 1][10];
for (int i = 0; i < 10; i++) {
dp[1][i] = 1L;
}
long result =0;
for (int i = 1; i <= 9; i++) {
result += recur(k, i);
}
System.out.println(result % 1000000000);
}
//digit 는 자릿수, val은 자릿값을 의미함
static long recur(int digit, int val) {
if (digit == 1) {
return dp[digit][val];
}
if (dp[digit][val] == null) {
// val이 0일경우 다음은 1밖에 못옴
if (val == 0) {
dp[digit][val] = recur(digit - 1, 1);
// val이 9일경우 다음은 8밖에 못옴
} else if (val == 9) {
dp[digit][val] = recur(digit - 1, 8);
// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
} else {
dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
}
}
return dp[digit][val] % 1000000000;
}
}
1) N번째 자릿수의 자릿값이 0인 경우 : 다음 자릿수의 자릿값은 1밖에 올 수 없다.
2) N번째 자릿수의 자릿값이 9인 경우 : 다음 자릿수의 자릿값은 8밖에 올 수 없다.
N 번째 자릿수의 자릿값이 없으면 N-1번째 자릿수를 탐색하고, N-1 도 없으면 N-1의 -1 번째 자릿수를 탐색하여 값이 있을 때 까지 찾아나가는 방식