#include <fstream>
#include <cstring>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
int B[100005],len;
char Str[100005];
int A,C,MOD,Sol[15];
bool Bit[400005];
void Read()
{
    f.getline(Str,100005);
    len=strlen(Str);
    int i;
    i=max(0,len-9);
    while(i<len)
    {
        A=A*10+Str[i]-'0';
        ++i;
    }
    memset(Str,0,sizeof(Str));
    f.getline(Str,100005);
    len=strlen(Str);
    for(int i=0;i<len;i++)
    {
        int dig;
        if(Str[i]>='0' && Str[i]<='9')
            dig=Str[i]-'0';
        else
            dig=Str[i]-'A'+10;
        for(int j=0;j<4;j++)
            Bit[(len-i-1)*4+j+1]=((dig & (1<<j))!=0);
    }
    f>>C;
    MOD=1;
    for(int i=1;i<=C;i++)
        MOD*=10;
    A%=MOD;
}

void Solve()
{
    len*=4;
    int result=0,shift=A,Sum=A;
    for(int i=1;i<=len;i++)
    {
        if(Bit[i]==1)
            result=(1LL*result*shift+Sum)%MOD;
        Sum=(1LL*Sum*(shift+1))%MOD;
        shift=(1LL*shift*shift)%MOD;
    }
    while(result>0)
    {
        Sol[++Sol[0]]=result%10;
        result/=10;
    }
    Sol[0]=C;
    for(int i=Sol[0];i>=1;i--)
        g<<Sol[i];
    g<<"\n";

}
int main()
{
    Read();
    Solve();
    return 0;
}