#include <stdio.h>
#include <stdlib.h>

long long int binaryEpansion(int basis, int exponent, int mod)
{
  long long int result = 1;
  for(int bit=63; bit >= 0; bit--)
  {
    result *= result;
    if ( (exponent & (1 << bit)) != 0 )
    {
      result *= basis;
    }
    result = result % mod;
  }
  return result;
}

int main(int argc, char** argv)
{
  if ( argc != 4 )
  {
    printf("Usuage: %s [basis] [exponent]\n", argv[0]);
    exit(1);
  }
  printf("%i\n", binaryEpansion(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])));
}