Beautiful Sums

#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4")
#pragma GCC target ("popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define pb push_back
#define FER(i,a,b) for(int i = ll(a); i < ll(b); ++i)
#define IFR(i,a,b) for(int i = ll(a); i >= ll(b); --i)
#define all(v) (v).begin(),(v).end()
#define mp make_pair
#define ff first
#define ss second
#define tm1 first
#define tm2 second.first
#define tm3 second.second
#define fill(x,v) memset(x,v,sizeof(x))
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sqr(x) (x)*(x)
#define bas 987625403
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ll,ii> tri;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define trace(...) fff(#__VA_ARGS__,__VA_ARGS__)

const int oo = 1e9;
template<typename t> void fff(const char *x, t&& val1){
   cout << x << " : " << val1 << endl;
}

template<typename t1, typename... t2> void fff(const char *x, t1&& val1, t2&&... val2){
   const char *xd = strchr(x+1,',');
   cout.write(x,xd-x)<< " : " << val1 << " | ";
   fff(xd+1,val2...);
}

const int MAX = 1e5;
int is[MAX + 1], sp[MAX + 1];
vector<ll> pri;

void criba(){
    for(ll i = 2; i <= MAX; i ++){
        if(!is[i]){
            sp[i] = i;
            if(i != 2) pri.pb(i);
            for(ll j = 2 * i; j <= MAX; j += i){
                if(!sp[j]) sp[j] = i;
                is[j] = 1;
            }
        }
    }
}

vector<ll> facts;
map<int, vector<int> > factsMap;
const ll MOD = 1e9 + 9;

void factorize(ll n){
    for(ll x = 1; x <= n; x ++){
        if(n % x == 0) facts.pb(x);
    }
    for(ll i = 0; i < sz(facts); i ++){
        for(ll x = 2; x <= facts[i]; x ++){
            if(facts[i] % x == 0) {
                factsMap[facts[i]].pb(x);
            }
        }
    }
}

ll cur[22], ans[22];
ld low = 1e300;

void go(ll lastk, ll index, ll remprod, ld acc){
    if(remprod == 1){
        if(acc < low){
            low = acc;
            FER(i, 0, index) ans[i] = cur[i];
            ans[index] = -1;
        }
        return;
    }
    for(ll i = 0; i < sz(factsMap[remprod]); i ++){
        ll k = factsMap[remprod][i];
        if(k > lastk) break;
        cur[index] = k;
        go(k, index + 1, remprod / k, acc + (k - 1) * log(pri[index]));
    }
}

ll bp(ll base, ll expo){
    if(expo == 0) return 1;
    if(expo % 2) return (base * bp(base, expo - 1))%MOD;
    ll val = bp(base, expo / 2);
    return sqr(val) % MOD;
}

int main(){
    fastio;
    criba();
    ll n; cin >> n;
    factorize(n);
    go(1e9, 0, n, 0);
    int pos = 0;
    ll ret = 1;
    while(ans[pos] != -1){
        ret *= bp(pri[pos], ans[pos] - 1);
        ret %= MOD;
        pos ++;
    }
    cout << ret << endl;
    return 0;
}