#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long an=0,MOD=1;
int c;
char a[100005],b[50005];
int indx=0;
bool bn[200005];
void citire()
{
    scanf("%s\n%s\n%d",&a,&b,&c);
    for(int i=1;i<=c;i++)
        MOD*=10;
    for(int i=0;i<strlen(a);i++)
        an=((an*10)%MOD+(a[i]-'0'))%MOD;

    for(int i=0;i<strlen(b);i++)
    {
        int aux;
        if(b[i]>='0'&&b[i]<='9')
            aux=b[i]-'0';
        else
            aux=10+b[i]-'A';
        for(int j=0;j<4;j++)
        {
            bn[++indx]=(aux&(1<<j));
        }
    }
}
void solve()
{
    long long rez=0,ap=an,sum=an;
    for(int i=1;i<=indx;i++)
    {
        //printf("%d ",bn[i]);
        if(bn[i])
        {
            rez=((rez*ap)%MOD+sum)%MOD;
        }
        sum=(sum*(ap+1))%MOD;
        ap=(ap*ap)%MOD;
    }
    printf("%lld\n",rez);
}
int main()
{
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);
    citire();
    solve();
    return 0;
}