#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
string s,B;
bitset<200005> b;
long long mod,ans;
long long rez[200005],p[200005];
int cif,c,i,len,n,num,j,k,lst;
int main()
{
    ifstream f("calcul.in");
    ofstream g("calcul.out");
    f>>s;
    f>>B;
    f>>c;
    mod=1;
    for(i=1;i<=c;i++)
        mod*=10;
    len=s.size();
    for(i=max(0,len-c);i<len;i++)
        n=n*10+(s[i]-'0');
    for(i=B.size()-1;i>=0;i--)
    {
        if(B[i]>='0'&&B[i]<='9')num=B[i]-'0';
        else num=B[i]-'A'+10;
        for(j=0;j<4;j++)
            {
                k++;
                if(((1<<j)&num))
                {
                    b[k]=1;
                    lst=k;
                }
            }
    }
    rez[lst]=n;p[lst]=n;
    for(i=lst-1;i>=1;i--)
    {
        rez[i]=1LL*(rez[i+1]+(p[i+1]*rez[i+1])%mod)%mod;
        p[i]=(1LL*p[i+1]*p[i+1])%mod;
        if(b[i])
            p[i]=(1LL*p[i]*n)%mod;
        if(b[i])
            rez[i]=(rez[i]+p[i])%mod;
    }
    ans=rez[1];
    while(rez[1]!=0)
    {
        rez[1]/=10;
        cif++;
    }
    if(ans==0)
        cif=1;
    for(i=1;i<=c-cif;i++)
       g<<'0';
    g<<ans;
    return 0;
}