import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int num = Integer.parseInt(br.readLine());

        int[][] arr = new int[101][10];

        for(int i=1;i<10;i++) {
        	arr[1][i] = 1;
        }

        for(int i=2;i<=num;i++) {
        	for(int j=0;j<10;j++) {
        		if(j==0) arr[i][j] = arr[i-1][j+1];
        		else if(j==9) arr[i][j] = arr[i-1][j-1];
        		else {
        			arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1];
        		}
        		arr[i][j] = arr[i][j]%1000000000;
        	}
        }

        int res = 0;
        for(int i=0;i<10;i++) {
        	res = res+arr[num][i];
        	res = res%1000000000;
        }

        bw.write(res+"");
        bw.flush();
        bw.close();
    }
}