#include <iostream>
using namespace std;

ifstream in ("lgput.in");
ofstream out ("lgput.out");
int main()
{
    long long n,p,r;
    in<<n;
      while(p)
      {
          if(p%2==0)
            {p=p/2;
             n=(n*n)/1999999973}
          else
            {p=p-1;
             r=r*n;}

    out>>(n*r)%1999999973;
      }

    return 0;
}