BAEKJOON_10844

import java.io.*;
import java.sql.Array;
import java.util.*;


public class Main {
    static long mod =1000000000L;
    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 N = Integer.parseInt(br.readLine());

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

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

        for(int i=2; i<N+1; i++){
            for(int j=0; j<10; j++){
                dp[i][j] =0;
                if(j-1>=0)dp[i][j] = dp[i][j] + dp[i-1][j-1];
                if(j+1<=9)dp[i][j] = dp[i][j] + dp[i-1][j+1];
                dp[i][j] %= mod;
            }
        }
        long ans=0;
        for(int i=0; i<10; i++){
            ans+=dp[N][i];
        }
        ans%=mod;
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }

}