#include <cstdio>
#include <cstring>
#include <iostream>
#define DEBUG 0
using namespace std;
int b[200010],pow[200010],calcul[200010],solve[200010];
char a[100010], s[100010];
void updcf (int &elem,int cf){
    b[elem+1]=cf%2;
    cf/=2;
    b[elem+2]=cf%2;
    cf/=2;
    b[elem+3]=cf%2;
    cf/=2;
    b[elem+4]=cf%2;
    cf/=2;
    elem+=4;
}
int main()
{
    FILE *fin=fopen ("calcul.in","r");
    FILE *fout=fopen ("calcul.out","w");
    int x,elem,i,c,n,mod;
    int soll=0,pa=1,bb,aa;
    if (DEBUG){
        fscanf (fin,"%d%d%d",&aa,&bb,&c);
        mod=1;
        for (i=1;i<=c;i++)
            mod=(mod*10);
        for (i=1;i<=bb;i++){
            pa=((long long)pa*aa)%mod;
            soll=(soll+pa)%mod;
        }
        fprintf (fout,"%d",soll);
        return 0;
    }
    fgets (a,100001,fin);
    x=strlen(a)-2;
    fgets (s,50001,fin);
    elem=0;
    for (i=strlen(s)-2;i>=0;i--){
        if ('0'<=s[i] && s[i]<='9')
            updcf(elem,s[i]-'0');
        else updcf(elem,10+s[i]-'A');
    }
    fscanf (fin,"%d",&c);
    n=0;
    mod=1;
    for (i=1;i<=c;i++)
        mod=(mod*10);
    for (i=max(0,x-c+1);i<=x;i++){
        n=n*10+(a[i]-'0');
    }
    /// n ^ 1 + ... + n ^ b
    pow[0]=n;
    for (i=1;i<=elem;i++) /// n ^ (2 ^ i)
        pow[i]=((long long)pow[i-1]*pow[i-1])%mod; /// pow ok
    while (b[elem]==0)
        elem--;
    for (i=elem;i;i--){
        if (i==elem)
            calcul[i]=n; /// n ^ (2^0)
        else{
            calcul[i]= ((long long)calcul[i+1] * calcul[i+1])%mod ;
            if (b[i]==1)
                calcul[i]=((long long) calcul[i]* n)%mod;
        }
    }
    /// calcul[i] = n ^ [ nr format din b cu i .. elem ]
    /// b[elem] = cel mai semnificativ
    /// calcul vector solve[i], solutia  pt bitii i,elem
    for (i=elem;i;i--){
        if (b[i]==1){ /// b impar
            solve[i] =( n +  ( (long long)n * ((long long)solve[i+1] * (1 + calcul[i+1]))%mod )%mod)%mod;
        }
        else { /// b par
            solve[i] = ((long long)solve[i+1] * (1 + calcul[i+1]))%mod;
        }
    }
    int c2=solve[1],cf=0;
    while (c2){
        cf++;
        c2/=10;
    }
    for (i=cf+1;i<=c;i++)
        fprintf (fout,"0");
    fprintf (fout,"%d",solve [1]);
    return 0;
}