/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;


public class P03BigMod {

  private static final String FileInputName = "bigmod.in";
  private static final String FileOutputName = "bigmod.out";

  private static long bigMod(long b, long p, long m) {
    if (0 == p)
      return 1;
    if (0 == b)
      return 0;
    if (1 == b || 1 == p)
      return b % m;
    if (1 == m)
      return 0;
    if (0 == p % 2) {
      long aux;
      aux = bigMod(b, p / 2, m);
      return (aux * aux) % m;
    } else
      return (bigMod(b, p - 1, m) * (b % m)) % m;

  }

  /**
   * @param args
   * @throws IOException
   */
  public static void main(String[] args) throws IOException {
    Scanner sc = null;
    PrintStream out = null;
    try {
      out = new PrintStream(new File(FileOutputName));
      sc = new Scanner(new File(FileInputName));
      while (sc.hasNextLong()) {
        long b = sc.nextLong();
        if (!sc.hasNextLong())
          break;
        long p = sc.nextLong();
        if (!sc.hasNextLong())
          break;
        long m = sc.nextLong();
        out.println(bigMod(b, p, m));
      }
    } finally {
      if (sc != null) {
        sc.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}