#include <cstdio>
#define BUF_SIZE 1<<17
#define MAXA 100000
#define MAXB 50000
char b[MAXB+1], q[MAXA+1];
long long m[2][2], r[2][2], aux[2][2];
char buf[BUF_SIZE];
FILE *fin;
int pos=BUF_SIZE;
inline char nextch(){
    if(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos=0;
    return buf[pos++];
}
int main(){
    int o, t, c, i, a, mod, x, j;
    char ch;
    FILE *fout;
    fin=fopen("calcul.in", "r");
    fout=fopen("calcul.out", "w");
    ch=nextch();
    o=0;
    while(ch!='\n'){
        q[++o]=ch;
        ch=nextch();
    }
    ch=nextch();
    t=0;
    while(ch!='\n'){
        b[++t]=ch;
        ch=nextch();
    }
    c=nextch()-'0';
    a=0;
    if(c>o) i=1;
    else i=o-c+1;
    while(i<=o){
        a=10*a+q[i]-'0';
        i++;
    }
    mod=1;
    for(i=0; i<c; i++) mod*=10;
    m[0][0]=m[1][0]=a;
    m[0][1]=0;
    m[1][1]=1;
    r[0][0]=r[1][1]=1;
    r[0][1]=r[1][0]=0;
    for(i=t; i>0; i--){
        if(('A'<=b[i])&&(b[i]<='Z')) x=b[i]-'A'+10;
        else x=b[i]-'0';
        for(j=0; j<4; j++){
            if(x&(1<<j)){
                aux[0][0]=(m[0][0]*r[0][0]+m[0][1]*r[1][0])%mod;
                aux[0][1]=(m[0][0]*r[0][1]+m[0][1]*r[1][1])%mod;
                aux[1][0]=(m[1][0]*r[0][0]+m[1][1]*r[1][0])%mod;
                aux[1][1]=(m[1][0]*r[0][1]+m[1][1]*r[1][1])%mod;
                r[0][0]=aux[0][0];
                r[0][1]=aux[0][1];
                r[1][0]=aux[1][0];
                r[1][1]=aux[1][1];
            }
            aux[0][0]=(m[0][0]*m[0][0]+m[0][1]*m[1][0])%mod;
            aux[0][1]=(m[0][0]*m[0][1]+m[0][1]*m[1][1])%mod;
            aux[1][0]=(m[1][0]*m[0][0]+m[1][1]*m[1][0])%mod;
            aux[1][1]=(m[1][0]*m[0][1]+m[1][1]*m[1][1])%mod;
            m[0][0]=aux[0][0];
            m[0][1]=aux[0][1];
            m[1][0]=aux[1][0];
            m[1][1]=aux[1][1];
        }
    }
    if(r[1][0]==0) for(i=0; i<c; i++) fputc('0', fout);
    else{
        while(10*r[1][0]<mod){
            fputc('0', fout);
            mod/=10;
        }
        fprintf(fout, "%lld\n", r[1][0]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}