//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)%k)*(f(n/2,k)%k))%k;
       else 
            t=(2*(f(n/2,k)%k)*(f(n/2,k)%k))%k;  
       return t;
}
int main()
{

   long long n=2;
   long long k=10;
  // for(int i=1;i<100;i++)
   cout<<f(i,k)<<"    "<<i<<endl;
  // long long z=(1<<62);
//   cout<<z;
   getchar();
   return 0;
}