#include <bits/stdc++.h>
#define ll long long
#define PI 3.14159265359
#define DP(x, y) memset(x, y, sizeof x)
#define all(x) x.begin(), x.end()
#define read(x) freopen("x", "r", stdin);
#define write(x) freopen("x", "w", stdout);

using namespace std;

ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
ll nC2(ll n) { return (n)*(n-1)/2; }
ll summing(ll n) { return (n)*(n+1); }

ll ans=0, mod=1e9 + 9;

map<char,vector<char>> mp;
map<char,ll>ind;
vector<char> v{'a', 'e', 'i', 'o', 'u'};
ll dp[5][200005];

ll counting(ll j, ll n, vector<char> &a, vector<char> &temp) {

    if (j == n) {
        return 1;
    }

    ll sum = 0;

    for (ll i=0; i<a.size(); i++) {

        if (~dp[ ind[a[i]] ][j]) {
            sum += dp[ ind[a[i]] ][j];
            continue;
        }

        temp.push_back(a[i]);

        dp[ind[a[i]]][j] = counting(j+1, n, mp[a[i]], temp)%mod;

        temp.pop_back();

        sum += dp[ind[a[i]]][j]%mod;
        sum %= mod;
    }

    return (sum%mod);
}

void solve() {

    ll n; cin >> n;

    DP(dp, -1);

    ind['a'] = 0;
    ind['e'] = 1;
    ind['i'] = 2;
    ind['o'] = 3;
    ind['u'] = 4;

    vector<char> c;
    mp['a'].push_back('e');

    mp['e'].push_back('a');
    mp['e'].push_back('i');

    mp['i'].push_back('a');
    mp['i'].push_back('e');
    mp['i'].push_back('o');
    mp['i'].push_back('u');

    mp['o'].push_back('i');
    mp['o'].push_back('u');

    mp['u'].push_back('a');

    ans = counting(0, n, v, c);

    cout << ans;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    ll t=1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}