#include<stdio.h>
#include<string.h>
#define tip unsigned long long
char ac[100100],bh[50100],bb[200100];
int c,L,LB,i,j,p;
tip a,M,sol,pp[200100],af[20];
void read(),solve();
int main()
{
    read();
    solve();
    return 0;
}
void read()
{
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);
    scanf("%s",ac);
    scanf("%s",bh);
    scanf("%d",&c);M=1;for(i=1;i<=c;i++)M*=10;
}
void solve()
{
    L=strlen(ac);
    if(L<c)p=0;else p=L-c;
    for(i=p;i<L;i++)
    {
        a*=10;
        a+=ac[i]-'0';
    }
    L=strlen(bh);
    for(i=0;i<L;i++)
        bh[i]=(bh[i]>='A')?bh[i]-'A'+10:bh[i]-'0';
    for(i=L-1;i>=0;i--)
        for(j=0;j<4;j++)
        {
            bb[LB++]=bh[i]&1;
            bh[i]>>=1;
        }
    while(!bb[LB-1])LB--;
    pp[0]=a;
    for(i=1;i<=LB;i++)pp[i]=(pp[i-1]*pp[i-1])%M;
     
    sol=1;
    for(i=LB-2;i>=0;i--)
    {
        sol=(sol*(pp[i]+1))%M;
        if(bb[i])
        {
            sol=(sol*pp[i])%M;
            sol=(sol+1)%M;
        }
    }
    sol=(sol*a)%M;
    for(i=1;i<=c;i++){af[i]=sol%10;sol/=10;}
    for(i=c;i>=1;i--)printf("%llu",af[i]);printf("\n");
}