#include <fstream>

using namespace std;
long long lgput(long long n, long long exp, long long c)
{
   long long p=1;
   while(exp!=0)
   {
       if(exp%2==1)
       {
         p=(p*n)%c;
         exp--;
       }
       n=(n*n)%c;
       exp/=2;
   }
   return p;
}
ifstream fin("algebra2.in");
ofstream fout("algebra2.out");
int main()
{
    long long n; fin>>n;
    unsigned long long s;
    if(n%2==0)
    {
       s=n/2;
       s*=(n+1);
    }
    else
    {
        s=(n+1)/2;
        s*=n;
    }
    fout<<lgput(n, s,  1000000009);
    fin.close();
    fout.close();
    return 0;
}