#include <cstring>
#include <cstdio>
#include <vector>
#define N 500005

using namespace std;

long long a, mod=1, rez;
int c;
char s[N];
vector <int> b;

void calc_modulo()
{
    for(int i=1;i<=c;i++)
        mod=mod*10;
}

void calc_baza()
{
    int st=(strlen(s)>9?strlen(s)-9:strlen(s));
    for(int i=st-1;i<strlen(s);i++)
        a=a*10+s[i]-'0';
}

void calc_putere()
{
    for(int i=0;i<strlen(s);i++)
    {
        int var;
        if(s[i]>='0' && s[i]<='9')
            var=s[i]-'0';
        else
            var=s[i]-'A'+10;
        for(int i=3;i>=0;i--)
            if(var&(1<<i))
                b.push_back(1);
            else
                b.push_back(0);
    }
}

void calc_rez()
{
    long long x=1;
    for(int i=0;i<b.size();i++)
    {
        rez=(rez*(x+1))%mod;
        x=(x*x)%mod;
        if(b[i])
        {
            x=(x*a)%mod;
            rez=(rez+x)%mod;
        }
    }
}

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

    scanf("%s\n", s);
    calc_baza();
    s[0]='\0';
    scanf("%s\n%d\n", s, &c);
    calc_modulo();
    a=a%mod;
    calc_putere();
    calc_rez();
    printf("%lld ", rez%mod);
    return 0;
}