#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N=1000005;
typedef long long ll;

char str[N];

int phi(int n)
{
    int rea = n;
    for(int i=2; i*i<=n; i++)
    {
        if(n % i == 0)
        {
            rea = rea - rea / i;
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1)
        rea = rea - rea / n;
    return rea;
}

ll multi(ll a,ll b,ll m)
{
    ll ans = 0;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = (ans + a) % m;
            b--;
        }
        b >>= 1;
        a = (a + a) % m;
    }
    return ans;
}

ll quick_mod(ll a,ll b,ll m)
{
    ll ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = multi(ans,a,m);
            b--;
        }
        b >>= 1;
        a = multi(a,a,m);
    }
    return ans;
}

void Solve(ll a,char str[],ll c)
{
    ll len = strlen(str);
    ll ans = 0;
    ll p = phi(c);
    if(len <= 15)
    {
        for(int i=0; i<len; i++)
            ans = ans * 10 + str[i] - ‘0‘;
    }
    else
    {
        for(int i=0; i<len; i++)
        {
            ans = ans * 10 + str[i] - ‘0‘;
            ans %= p;
        }
        ans += p;
    }
    printf("%I64d\n",quick_mod(a,ans,c));
}

int main()
{
    ll a,c;
    while(~scanf("%I64d%s%I64d",&a,str,&c))
        Solve(a,str,c);
    return 0;
}