#include <stdio.h>
int num[101][10]={0};
int top_down(int l,int n) {

    if(l==1) {
        return (n==0) ? 0 : 1;
    }
    if(num[l][n]!=0) return num[l][n];
    
    if(n==0) num[l][n] = top_down(l-1,1);
    else if(n==9) num[l][n] = top_down(l-1,8);
    else num[l][n]=(top_down(l-1,n-1)+top_down(l-1,n+1))%1000000000;
    return num[l][n]%1000000000;
}


int main() {
    int n;
    scanf("%d",&n);
   
    long long total_sum = 0;
    // 계단수는 마지막 자리가 0~9인 모든 경우의 합입니다.
    for (int i = 0; i <= 9; i++) {
        total_sum = (total_sum + top_down(n, i)) % 1000000000;
    }

    printf("%lld\n", total_sum);
    return 0;
}