import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[][] answers;
public static void main(String... args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer tokenizer = new StringTokenizer(br.readLine());
br.close();
int n = Integer.parseInt(tokenizer.nextToken());
answers = new int[n+1][10];
for (int i = 1; i < 10; i++) {
answers[1][i] = 1;
}
int answer = 0;
for (int i = 0; i < 10; i++) {
answer += f(n, i) ;
answer %= 1000000000 ;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
static int f(int n, int d) {
if (n < 0) {
return 0;
}
if (answers[n][d] != 0) {
return answers[n][d];
}
if (d == 0) {
answers[n][d] = f(n-1, d+1);
} else if (d == 9) {
answers[n][d] = f(n-1, d-1);
} else {
answers[n][d] = f(n-1, d-1) + f(n-1, d+1);
}
answers[n][d] %= 1000000000;
return answers[n][d];
}
}