#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 200005
using namespace std;

int n,sol;
char A[maxn],B[maxn],a[maxn],C;

void read()
{
    scanf("%s\n",A+1);
    scanf("%s %d",B+1,&C);
}

void solve()
{
    int Ac=0,Sc,MOD;

    int nr=strlen(A+1);
    long long f=1;

    MOD=1;
    for(int i=1;i<=C;i++) MOD*=10;

    for(int i=nr;i && C;i--,C--,f*=10)
     Ac+=f*(A[i]-'0');

    int x;
    nr=strlen(B+1);
    for(int i=1;i<=nr;i++)
    {
        if(B[i]>='0' && B[i]<='9') x=B[i]-'0';
        else x=B[i]-'A'+10;

        for(int j=3;j>=0;j--)
         a[++n]=((x>>j)&1);
    }

    Sc=Ac;
    for(int i=n;i;i--)
    {
        if(a[i]) sol=(1LL*sol*Ac+Sc)%MOD;
        Sc=(1LL*Sc*(1+Ac))%MOD;
        Ac=(1LL*Ac*Ac)%MOD;
    }
}

int main()
{
    freopen("calcul.in","r",stdin);
    freopen("calcul.out","w",stdout);

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}