#include <gmpxx.h>
#include <iostream>

using namespace std;

typedef mpz_class mpz;

/**Could not find how to get the number
 * of bits of a mpz.
 *
 * I think it exists?, but I don't want
 * to search forever...*/
unsigned long int mpz_nrbits (const mpz_t op)
{
	unsigned long int bit=0;
	unsigned long int dec=mpz_popcount(op);

	if (dec==0) return 0;

	bit = mpz_scan1(op, bit);

	do {
		// cout << dec << " bit: " << bit << endl;
		if (--dec <= 0) return bit+1;
	} while (bit=mpz_scan1(op, bit+1));
}

/**Fast exponentiation algorithm.
  */
mpz exp(const mpz &g, const mpz &exp, const mpz &n)
{
	mpz e = exp%(n-1);

	mpz b = 1;
	if (e==0) return b;

	mpz G=g;
	if (mpz_tstbit(e.get_mpz_t(), 0)) b=g;

	for (unsigned long int i=1; i<mpz_nrbits(e.get_mpz_t()); i++)
	{
		G = (G*G)%n;
		if (mpz_tstbit(e.get_mpz_t(),i)) b=(b*G)%n;
	}
}

int main()
{
	mpz g,e,n;
	cin >> g >> e >> n;

	cout << exp(g,e,n) << endl;

	return 0;
}