#include <stdio.h>

int bottom_up(int n) {
    //dp[n(문자길이)][마지막 숫자]
    int dp[101][10]={0};
    //j=마지막 숫자
    for (int j=1; j<=9; j++) {
        dp[1][j]=1;
    }
    //문자 길이만큼
    for(int i=2; i<=n; i++) {
        //끝자리가 0이랑 9일때 1번씩 더함
        for(int j=0; j<=9; j++) {
            if (j==0) {
                //끝자리가 0이면 앞은 무조건 1
                dp[i][j]=dp[i-1][1]%1000000000;
            } else if(j==9) {
                //끝자리가 9이면 앞은 무조건 8
                dp[i][j]=dp[i-1][8]%1000000000;
            } else {
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
            }
        }
    }
    int sum=0;
    for(int j=0; j<=9; j++) {
        sum=(sum+dp[n][j])%1000000000;
    }
    return sum;
}

int main() {
    int n;
    scanf("%d",&n);
    printf("%d",bottom_up(n));
    return 0;
}