#include<cstdio>
#include<cstring>
#define MAXN 200010
using namespace std;
char s[MAXN],b[MAXN];
int bit[MAXN];
int main(){
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);
    int i,j,c,n,mask,bits=0;
    long long mod=1,a=0,x=1,answer=0;
    scanf("%s%s%d",s,b,&c);
    for(i=1;i<=c;i++)
        mod*=10;
    n=strlen(s);
    for(i=0;i<n;i++)
        a=(a*10+s[i]-'0')%mod;
    n=strlen(b);
    for(i=0;i<n;i++){
        if(b[i]>='A')
            mask=b[i]-'A'+10;
        else
            mask=b[i]-'0';
        for(j=3;j>=0;j--){
            bits++;
            bit[bits]=((mask>>j)&1);
        }
    }
    for(i=1;i<=bits;i++){
        answer=(answer*(x+1))%mod;
        x=(x*x)%mod;
        if(bit[i]>0){
            x=(x*a)%mod;
            answer=(answer+x)%mod;
        }
    }
    for(i=1;i<c;i++){
        mod/=10;
        if(answer<mod)
            printf("0");
    }
    printf("%lld",answer);
    return 0;
}