#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define pi pair<int,int>
#define pl pair<ll,ll>

using namespace std;
ifstream fin("calcul.in");
ofstream fout("calcul.out");

const ll N=5e4+5,INF=1e18,M=1e2+5,inf=INT_MAX;

string a,b;
int c,cnt;
ll nr,MOD=1;
bool bits[4*N];

int main()
{
    fin>>a>>b>>c;
    for(int i=1;i<=c;i++)
    {
        MOD*=10;
    }
    int n=a.size();
    for(int i=max(n-c,0);i<n;i++)
    {
        nr=nr*10+a[i]-'0';
    }
    for(int i=0;i<b.size();i++)
    {
        int x;
        if(b[i]>='0'&&b[i]<='9')x=b[i]-'0';
        else if(b[i]>='A'&&b[i]<='F')x=b[i]-'A'+10;

        for(int j=3;j>=0;j--)
        {
            bits[++cnt]=((x>>j)&1);
        }
    }
    ll ans=0,x=1;
    for(int i=1;i<=cnt;i++)
    {
        ans=ans*(x+1)%MOD;
        x=x*x%MOD;
        if(bits[i])
        {
            x=x*nr%MOD;
            ans+=x;
            if(ans>=MOD)ans-=MOD;
        }
    }
    MOD/=10;
    while(ans<MOD)
    {
        fout<<'0';
        MOD/=10;
    }
    if(MOD)
    {
        fout<<ans;
    }

}