/*

 高次同余第一题：

 大牛提起过这道题，当时觉得b太大了10^1000000，无从下手。

 a^b%c=a^(b%phi(c))%c ,注意a==c的情况

 这句话，想起了  费马小定理 a^b%c=a^(b%(c-1))%c;  c是互数，a,c互质的时候。

 费马小定理是一个特殊的总结吧。这个是通式。

 */

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 char b[];

 __int64 Euler(__int64 n)

 {

     __int64 i,temp=n;

     for(i=;i*i<=n;i++)

     {

         if(n%i==)

         {

             while(n%i==)

             n=n/i;

             temp=temp/i*(i-);

         }

     }

     if(n!=) temp=temp/n*(n-);

     return temp;

 }

 __int64 power_sum2(__int64 a,__int64 n,__int64 mod)

 {

     __int64 ans=;

     while(n)

     {

         if(n&)

         {

             ans=(ans*a)%mod;

         }

         n=n>>;

         a=(a*a)%mod;

     }

     return ans;

 }

 int main()

 {

     __int64 a,c,len,k,cur,i;

     while(scanf("%I64d",&a)>)

     {

         scanf("%s",b+);

         scanf("%I64d",&c);

         if(a==c)

         {

             printf("0\n");

             continue;

         }

         len=strlen(b+);

         k=Euler(c);

         for(i=,cur=;i<=len;i++)

         {

             cur=cur*+b[i]-'';

             cur=cur%k;

         }

         printf("%I64d\n",power_sum2(a%c,cur,c));

     }

     return ;

 }