#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;
long long expo(long long a, long long b)
{
    long long result = 1;

    while (b)
    {
        if (b&1)
        {
            result=result*a%1000000009;
        }
        b >>=1 ;
        a=a*a%1000000009;
    }
    return result;
}

int main()
{
    freopen ("lgput.in","r",stdin);
    freopen ("lgput.out","w",stdout);
    long long n,b;
    scanf("%lld",&n);
    if(n%2==0)
    {
        b=expo(n,n/2);
        printf("%lld",expo(b,n+1));
    }
    else
    {
        b=expo(n,(n+1)/2);
        printf("%lld",expo(b,n));
    }






    return 0;
}