MOS_G

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const ll mod = 1e7;

int main() {
    int n;
    cin >> n;
    vector<vector<ll>> dp(n, vector<ll> (9));
    vector<vector<ll>> sum(n, vector<ll> (9));
    for(int i = 0; i < min(n, 9); ++i){
        dp[0][i] = 1;
    }
    sum[0][0] = 1;
    for(int i = 1; i < 9; ++i){
        sum[0][i] = sum[0][i - 1] + dp[0][i];
    }
    for(int i = 1; i < n; ++i){
        if(i % 2 == 1){
            dp[i][0] = 0;
        }
        else{
            dp[i][0] = sum[i - 1][8];
        }
        for(int j = 1; j < min(n, 9); ++j){
            if(i % 2 == 1){
                dp[i][j] = (sum[i - 1][j - 1]) % mod;
            }
            else{
                dp[i][j] = (sum[i - 1][8] - sum[i - 1][j]) % mod;
            }
        }
        sum[i][0] = dp[i][0];

        for(int j = 1; j < 9; ++j){
            sum[i][j] = (sum[i][j - 1] + dp[i][j]);
        }
    }

    cout << sum[n - 1][8] % mod << "\n";
}