import Prog1Tools.IOTools;
public class RekPot   //Name muss gleich Dateinamen sein!!
                       // Hier die rekursive Potenz.
			{
  public static int Pot(int a, long b, int m)  // Nur fuer a, b >= 0!!
  {
    int x;
    if (b == 0)  return 1;
    if ((b%2) == 0) { 
    x = Pot(a, b/2, m);
    return((x * x)% m);
    }
    else return((a * Pot(a, b-1, m))%m);
    }
  public static void main(String[] args)
  {
   int n, m; 
   long k;
   n =  IOTools.readInteger("n= ");
   k =  IOTools.readInteger("k= ");
   m =   IOTools.readInteger("m= " );
   System.out.println(n + " hoch" + k+ "mod" + m + "ist" +
                       Pot(n,k,m ));   
   
   }
 }