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

/* Valeur absolue de a */
int absolue(int a) {
  if (a>0) return a;
  else return -a;
}
/* Une première version d'un tirage uniforme */
int uniforme1(int a) {
  if (a == 0) return 0;
  else return rand()%absolue(a);
}

/*
Si RAND_MAX+1 n'est pas divisible par a, on a perdu en uniformité. En
effet, les entiers entre 0 et (RAND_MAX % a) ont une plus grande
probabilité d'apparaître.

Pour vous convaincre, regardons RAND_MAX = 10 et cherchons à tirer un
nombre entre 0 et 2. Alors :
 - 0,3,6,9 sont envoyés sur 0
 - 1,4,7,10 sont envoyés sur 1
 - 2,5,8 sont envoyés sur 2 : 2 est moins probable que les autres...
*/

int uniforme(int a) {
  int x=rand();
  int absa = absolue(a);
  /*
    Tant qu'on est dans la zone entre RAND_MAX-RAND_MAX%a et RAND_MAX,
    on tire un nouveau x.
   */
  while(x >= (RAND_MAX/absa)*absa)
    x = rand();
  return x%absa;
}

int simule(int a, int n) {
  int z = 0;
  int i;
  for(i=0;i<n;i++)
    if (uniforme(a) == 0) z++;
  return z;
}

/* Cette version de puissance fait b multiplications. */
int puissance(int a, int b) {
  int i,r=1;
  for(i=0;i<b;i++)
    r*=a;
  return r;
}

/* Cette version de puissance fait b multiplications. */
int puissance_mod(int a, int b, int n) {
  int i,r=1;
  for(i=0;i<b;i++)
    r=(r*a) % n;
  return r;
}


int puissance_rapide(int a, int b) {
  int res=1;
  int c=a, e=b;

  /* 
     On peut vérifier que dans la boucle, on a en permanence res*c^e =
     a^b. Donc à la fin de la boucle, comme e=0, on sait que res =
     a^b ! On fait moins de 3log(b) multiplications.
   */
  while(e>0) {
    if (e%2 == 0) {
      e = e/2;
      c = c*c;
    }
    else {
      e--;
      res *= c;
    }
  }
  return res;
}

int puissance_rapide_mod(int a, int b, int n) {
  int res=1;
  int c=a % n, e=b;

  while(e>0) {
    if (e%2 == 0) {
      e = e/2;
      c = (c*c) % n;
    }
    else {
      e--;
      res = (res*c) % n;
    }
  }
  return res;
}

/* On peut l'écrire récursivement */
int puissance_rec(int a, int b, int r) {
  if (b == 0) return r;
  else if (b%2 == 0) return puissance_rec(a*a,b/2,r);
  else return puissance_rec(a,b-1,r*a);
}

int main() {
  int a=1,b,m;
  while(a!=0) {
    scanf("%d %d %d",&a,&b,&m);
    printf("%d\n",puissance_rapide_mod(a,b,m));
  }
  return 0;
}