import Foundation

let N: Int = Int(readLine()!)!
let MOD: Int = 1000000000

if N < 10 {
    print(0)
    exit(0)
}

var dp: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: 0, count: 1024), count: 10), count: N+1)
for n in 1...9 {
    dp[1][n][1<<n] = 1
}

for length in 1..<N {
    for num in 0...9 {
        for bit_state in 0..<1024 {
            if dp[length][num][bit_state] == 0 {
                continue
            }
            
            var next = num - 1
            if next >= 0 {
                let next_bit_state = bit_state | (1<<next)
                dp[length+1][next][next_bit_state] += dp[length][num][bit_state]
                dp[length+1][next][next_bit_state] %= MOD
            }
            
            next = num + 1
            if next < 10 {
                let next_bit_state = bit_state | (1<<next)
                dp[length+1][next][next_bit_state] += dp[length][num][bit_state]
                dp[length+1][next][next_bit_state] %= MOD
            }
        }
    }
}

var ans = 0
for n in 0...9 {
    ans = (ans + dp[N][n][1023])%MOD
}
print(ans)