// teste da classe Integer (precisao ilimitada)

#include <iostream.h>
#include <Integer.h>
 
Integer exp_mod (Integer a, Integer e, Integer b) {
  Integer p;
  Integer r;
  p = a;
  r = 1;
  while (e != 0) {
    if ( e % 2 == 1) {
      r = (r*p) % b;
    }
    p = (p*p) % b;
    e = e/2;
  }

  return r;  exit(0);
}

main(int argc, char ** argv) {
  Integer a;
  Integer e;
  Integer b;
  
  if (argc != 3) {
    cout << "Usage: " << argv[0] << " <b> <e>\n";
    exit(1);
  }

  b = atoI(argv[1]);
  e = atoI(argv[2]);

  while (cin >> a) {
    cout << exp_mod(a,e,b) << "\n";
  }

  exit(0);
}