#include<stdio.h>
#include<string.h>
#define Lgam 100002
#define Lgbm 50002
#define max(a,b) ((a)>(b)?(a):(b))
char A[Lgam],B[Lgbm];
int P[Lgbm<<2],S[Lgbm<<2],c,ans;

void read()
{
    freopen("calcul.in","r",stdin);
    scanf("%s%s%d",A,B,&c);
}

void solve()
{
    int i,j,v,p=1,lga,lgb,mod=1;

    lga=strlen(A);
    for(i=max(lga-c,0);i<lga;++i)
        P[0]=P[0]*10+A[i]-'0';
    S[0]=P[0];
        
    for(i=0;i<c;++i)
        mod*=10;

    lgb=strlen(B);
    for(i=1;i<lgb<<2;++i)
    {
        P[i]=(long long)P[i-1]*P[i-1]%mod;
        S[i]=(long long)S[i-1]*(P[i-1]+1)%mod;
    }

    for(i=lgb-1;i>=0;--i)
    {
        v=B[i]>='0' && B[i]<='9'?B[i]-'0':B[i]-'A'+10;
        for(j=lgb-1-i<<2;j<lgb-i<<2;++j,v>>=1)
            if(v&1)
            {
                ans=(ans+(long long)S[j]*p)%mod;
                p=(long long)p*P[j]%mod;
            }
    }
}

int digits(int x)
{
    int d=0;

    do
    {
        ++d;
        x/=10;
    } while(x);
    
    return d;
}

void write()
{
    int i;

    freopen("calcul.out","w",stdout);
    for(i=c-digits(ans);i;--i)
        printf("0");
    printf("%d\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}