#include <vector>
#include <map>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
//typedef long double ld;
typedef vector<int> Vint;

const long double eps = 1e-10;
struct ld
{
    long double val;
    unsigned long long estimate;

    ld ()
    {
        val = 0;
        estimate = 0;
    }

    ld (ll _e)
    {
        val = logl((long double)_e);
        estimate = _e;
    }
};

ld operator * (const ld &left, const ld &right)
{
    ld ans;
    ans.val = left.val + right.val;
    ans.estimate = left.estimate * right.estimate;
    return ans;
}
bool operator < (const ld &left, const ld &right)
{
    if (left.val + eps < right.val)
        return true;
    if (left.val > right.val + eps)
        return false;

    unsigned long long diff = left.estimate - right.estimate;
    if (diff > (1ULL << 63))
        return true;
    return false;
}

const int mod = (int)1e9 + 9;
Vint gen_primes(int n)
{
    vector<char> isprime(n + 1, 1);

    Vint ans;
    for (int i = 2; i <= n; i++)
    if (isprime[i])
    {
        if (i != 2)
            ans.pb(i);
        for (int j = 2 * i; j <= n; j += i)
            isprime[j] = 0;
    }

    return ans;
}

ll powmod(ll x, ll y)
{
    ll res = 1;
    while (y)
    {
        if (y & 1)
        {
            y--;
            res *= x;
            res %= mod;
        }
        else
        {
            y >>= 1;
            x *= x;
            x %= mod;
        }
    }

    return res;
}

void solve(int n)
{
    const int bound = 20;
    Vint primes = gen_primes(200);

    primes.resize(bound);

    vector<Vint> divisors(n + 1);
    for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        divisors[j].pb(i);

    ld inf;
    inf.val = 1e18;
    inf.estimate = 0;

    vector<vector<ll> > dp(bound, vector<ll>(n + 1, 1));
    vector<vector<ld> > minval(bound, vector<ld>(n + 1, inf));
    vector<vector<ld> > Pows(bound, vector<ld>(n + 1, 1));

    for (int i = 0; i < bound; i++)
    for (int j = 1; j <= n; j++)
        Pows[i][j] = Pows[i][j - 1] * ld(primes[i]);

    ll curt = 1;
    ld other = 1;

    for (int i = 1; i <= n; i++)
    {
        dp[bound - 1][i] = curt;
        minval[bound - 1][i] = other;

        curt *= primes[bound - 1];
        curt %= mod;
        other = other * primes[bound - 1];
    }

    for (int it = bound - 2; it >= 0; it--)
    for (int x = 1; x <= n; x++)
    if (binary_search(divisors[n].begin(), divisors[n].end(), x))
    {
        int p = primes[it];
        for (int d : divisors[x])
        {
            ld cur = Pows[it][d - 1];

            if (cur * minval[it + 1][x / d] < minval[it][x])
            {
                minval[it][x] = cur * minval[it + 1][x / d];
                dp[it][x] = powmod(p, d - 1) * dp[it + 1][x / d];
                dp[it][x] %= mod;
            }
        }
    }

    cout << dp[0][n] << endl;
}

int main()
{
    int n;
    while (cin >> n)
        solve(n);
}