#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1e9 + 9;

int32_t main()
{
    int n;
    cin >> n;
    int cntc [n], cntw [n], cntsp [n], cnti[n];
    cntc[0] = 20;
    cntsp[0] = 0;
    cntw[0] = 10;
    cnti[0] = 1;
    for(int i = 1; i < n; i++){
        cntc[i] = cntw[i - 1] * 20 % mod;
        cnti[i] = cntw[i - 1];
        cntw[i] = ((cntc[i - 1] * 10) + (cntsp[i - 1] * 10) + cnti[i - 1] * 10) % mod;
        cntsp[i] = cntc[i - 1] * 2 % mod;
    }
    cout << (cntc[n - 1] + cntw[n - 1] + cntsp[n - 1] + cnti[n - 1]) % mod;
}