#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e5)+10;

int b[maxN],c,biti=0;
char a[maxN],s[maxN];
long long pw[maxN],sol[maxN];

inline void baga(int &biti,int val)
{
    b[biti+1]=val%2;
    val>>=1;

    b[biti+2]=val%2;
    val>>=1;

    b[biti+3]=val%2;
    val>>=1;

    b[biti+4]=val%2;
    val>>=1;

    biti+=4;
}
int main()
{
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);

    scanf("%s",a+1);
    scanf("\n");
    scanf("%s",s+1);
    scanf("%d",&c);
  //  cerr<<c<<'\n';
    int len=strlen(a+1);
    for(int i=strlen(s+1);i>=1;i--)
        if(isdigit(s[i]))
            baga(biti,s[i]-'0');
            else baga(biti,s[i]-'A'+10);

    long long mod=1LL;
    for(int i=1;i<=c;i++)
        mod=(mod*10LL);
    //cerr<<mod<<'\n';
    long long n=0LL;

    for(int i=max(1,len-c+1);i<=len;i++)
        n=(n*10)+1LL*(a[i]-'0');

    while(!b[biti]) biti--;


    for(int i=biti;i;i--)
    {
        if(i==biti)
            pw[i]=1LL*n;
            else
        {
            pw[i]=(pw[i+1]*pw[i+1])%mod;
            if(b[i]==1)
                pw[i]=(pw[i]*n)%mod;
        }
    }

  //  cerr<<"HERE"<<'\n';
    for(int i=biti;i>=1;i--)
    {
        if(b[i]==1)
        {
            sol[i]=(sol[i+1]*(1+pw[i+1]))%mod;
            sol[i]=(sol[i]*n)%mod;
            sol[i]=(sol[i]+n)%mod;
        }
            else sol[i]=(sol[i+1]*(1+pw[i+1]))%mod;

    }

    int r=sol[1],d=0;
    if(!r) d=1;
    while(r)
    {
        d++;
        r/=10;
    }

    for(int i=d+1;i<=c;i++)
        printf("0");
    printf("%lld\n",sol[1]);
    return 0;
}