#include<bits/stdc++.h>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char s[1<<17],b[1<<16];
int i,j,c,n,mask,bits,mod=1,a,x=1,sol,bit[1<<18];
int main(){
    f>>s>>b>>c;
    for(i=1;i<=c;i++) mod*=10;
    n=strlen(s);
    for(i=max(n-c,0);i<n;i++) a=a*10+s[i]-'0';
    n=strlen(b);
    for(i=0;i<n;i++){
        mask=((b[i]>='A')?b[i]-'A'+10:b[i]-'0');
        for(j=3;j>=0;--j)
            bit[++bits]=((mask>>j)&1);
    }
    for(i=1;i<=bits;++i){
        sol=1LL*sol*(x+1)%mod;
        x=1LL*x*x%mod;
        if(bit[i]>0)
        {
            x=1LL*x*a%mod;
            sol=(sol+x)%mod;
        }
    }
    mod/=10;
    while(sol<mod) g<<0,mod/=10;
    if(mod) g<<sol;
    return 0;
}