#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

ifstream fin("calcul.in");
ofstream fout("calcul.out");

unsigned long long n,i,j,a,mod,m,x,stop;
bool v[1200001];
char s[300001],c[300001];

unsigned long long calc(unsigned long long p,unsigned long long &A){
    if(p==stop){
       A=a;
       return A;
    }

    if(v[p]==0){
        unsigned long long x=calc(p-1,A),aux=A;
        A=(A*A)%m;

        return ( x*(1+aux) )%m;
    }else{
        v[p]=0;
        unsigned long long x=calc(p,A);
        A=(a*A)%m;

        return (a*(x+1))%m;
    }
}

int main(){
    fin>>s+1>>c+1;
    fin>>x;

    m=1;
    for(i=1;i<=x;i++)
        m*=10;

    n=strlen(s+1);

    for(j=1,i=n;i>max(n-x,0LL);j*=10,i--){
        a+=(s[i]-'0')*j;
    }

    //cout<<a<<"\n";

    n=strlen(c+1);
    for(i=1;i<=n;i++){
        j=(i-1)*4;

        if(c[i]=='0'){
            v[j+1]=0;
            v[j+2]=0;
            v[j+3]=0;
            v[j+4]=0;
        }
        if(c[i]=='1'){
            v[j+1]=0;
            v[j+2]=0;
            v[j+3]=0;
            v[j+4]=1;
        }
        if(c[i]=='2'){
            v[j+1]=0;
            v[j+2]=0;
            v[j+3]=1;
            v[j+4]=0;
        }
        if(c[i]=='3'){
            v[j+1]=0;
            v[j+2]=0;
            v[j+3]=1;
            v[j+4]=1;
        }
        if(c[i]=='4'){
            v[j+1]=0;
            v[j+2]=1;
            v[j+3]=0;
            v[j+4]=0;
        }
        if(c[i]=='5'){
            v[j+1]=0;
            v[j+2]=1;
            v[j+3]=0;
            v[j+4]=1;
        }
        if(c[i]=='6'){
            v[j+1]=0;
            v[j+2]=1;
            v[j+3]=1;
            v[j+4]=0;
        }
        if(c[i]=='7'){
            v[j+1]=0;
            v[j+2]=1;
            v[j+3]=1;
            v[j+4]=1;
        }
        if(c[i]=='8'){
            v[j+1]=1;
            v[j+2]=0;
            v[j+3]=0;
            v[j+4]=0;
        }
        if(c[i]=='9'){
            v[j+1]=1;
            v[j+2]=0;
            v[j+3]=0;
            v[j+4]=1;
        }
        if(c[i]=='A'){
            v[j+1]=1;
            v[j+2]=0;
            v[j+3]=1;
            v[j+4]=0;
        }
        if(c[i]=='B'){
            v[j+1]=1;
            v[j+2]=0;
            v[j+3]=1;
            v[j+4]=1;
        }
        if(c[i]=='C'){
            v[j+1]=1;
            v[j+2]=1;
            v[j+3]=0;
            v[j+4]=0;
        }
        if(c[i]=='D'){
            v[j+1]=1;
            v[j+2]=1;
            v[j+3]=0;
            v[j+4]=1;
        }
        if(c[i]=='E'){
            v[j+1]=1;
            v[j+2]=1;
            v[j+3]=1;
            v[j+4]=0;
        }
        if(c[i]=='F'){
            v[j+1]=1;
            v[j+2]=1;
            v[j+3]=1;
            v[j+4]=1;
        }
    }

    for(stop=0;v[stop]==0;stop++);
    //for(i=stop;i<=4*n;i++)
    //    cout<<v[i];

    x=calc(n*4,x);
    while(m!=1){
        if(x<m/10)
            fout<<0;
        else
            break;

        m/=10;
    }
    fout<<x;

    return 0;
}