export {};
const N: number = Number(require("fs").readFileSync(0).toString());
const MOD: number = 1000000000;

if(N < 10) {
    console.log(0);
    process.exit(0);
}

let dp: number[][][] = Array.from({length : N },
                 () => Array.from({length : 10}, () => new Array(1024).fill(0)
                )
            );

for(let n=1; n<=9; n++) {
    dp[0][n][1<<n] = 1;
}

for(let i=1; i<N; i++) {
    for(let n=0; n<10; n++) {
        for(let bit_state=0; bit_state < 1024; bit_state++) {
            if(dp[i-1][n][bit_state] === 0) continue;

            let next_num: number = n+1;
            let next_bit_state: number = bit_state | (1<<next_num);

            if(next_num < 10) {
                dp[i][next_num][next_bit_state] += dp[i-1][n][bit_state];
                dp[i][next_num][next_bit_state] %= MOD;
            }

            next_num = n-1;
            next_bit_state = bit_state | (1<<next_num);

            if(next_num >= 0) {
                dp[i][next_num][next_bit_state] += dp[i-1][n][bit_state];
                dp[i][next_num][next_bit_state] %= MOD;
            }
        }
    }
}

let ans: number = 0;
for(let n=0; n<10; n++) {
    ans += dp[N-1][n][1023];
    ans %= MOD;
}

console.log(ans);