//2^n.cpp
// Generating 2^n%k for very high values of n
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

long long f(long long n, long long k)
{
       long long t;
       if(n==0)
               return 1;
       
       else if (n%2==0)
       {
            t= f(n / 2 , k) ;
            t = ((t % k) * (t % k)) % k ;
       }
       else 
       {
            t = f (n / 2 , k);
            t= (2*(t % k)*(t % k))%k;  
       }
       return t;
}
int main()
{

  long long k=123456789;
  long long n = 10e18;
  cout<<f(n , k)<<endl;
   getchar();
   return 0;
}