#include <cstdio>
#include <cstring>
#include <iostream>

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,y;
    fgets (a,100001,fin);
    x=strlen(a)-2;
    fgets (s,50001,fin);
    elem=0;
    for (i=0;s[i]!='\n';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 (y=1;y<=elem;y++) /// n ^ (2 ^ y)
        pow[y]=((long long)pow[y-1]*pow[y-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]* pow[elem-i-1])%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;
        }
    }
    fprintf (fout,"%d",solve [1]);
    return 0;
}