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

// calculates potenz by basis and exponent
long long int binaryEpansion(long long int basis, long long int exponent)
{
  if (exponent == 0) return 1;
  if (exponent == 1) return basis;
  long long int result = 1;
  for(int bit = (sizeof(long long int) - 1); bit >= 0; bit--)
  {
    result *= result;
    if ( (exponent & (1 << bit)) != 0 )
    {
      result *= basis;
    }
  }
  return result;
}

// calculates (potenz by 'basis' and 'exponent') modulo 'mod'
long long int binaryEpansion(long long int basis, long long int exponent, long long int mod)
{
  long long int result = 1;
  for(int bit = (sizeof(long long int) - 1); 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 < 3 || argc > 4 )
  {
    printf("Usage: %s basis exponent [modulo]\n", argv[0]);
    exit(1);
  }

  // parse input
  long long int param[3];
  for(int arg = 1; arg < argc; arg++)
  {
    for(int pos = 0; argv[arg][pos] != 0; pos++)
    {
      param[arg-1] = ((argv[arg][pos] - '0') * binaryEpansion(10, pos));
    }
  }

  // print result(s)
  if (argc == 4) printf("parameter: %lld; %lld; %lld\nergebnis: %lld\n", param[0],param[1],param[2], binaryEpansion(param[0], param[1], param[2]));
  if (argc == 3) printf("parameter: %lld; %lld\nergebnis: %lld\n", param[0],param[1], binaryEpansion(param[0], param[1]));
}