#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct MyType
{
    long long si,ai;
};

char A[100010],B[50010];
int a, c, C;
bool b16[16][5];
bool b[200010];

MyType functie(int poz)
{
    MyType temp,rez;
    if(poz==-1)
    {
        rez.si=0;
        rez.ai=1;
    }
    else if(b[poz]==false) // par
    {
        temp=functie(poz-1);
        rez.si=temp.si+temp.ai*temp.si;
        rez.si%=c;
        rez.ai=temp.ai*temp.ai;
        rez.ai%=c;
    }
    else // impar
    {
        temp=functie(poz-1);
        rez.ai=(temp.ai*temp.ai)%c*a;
        rez.ai%=c;
        rez.si=temp.si+temp.si*temp.ai+rez.ai;
        rez.si%=c;
    }
   // printf("%d: %lld %lld\n",   poz, rez.si,     rez.ai);
    return rez;
}
int main()
{
    int i;
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);
    gets(A);
    gets(B);
    scanf("%d", &C);
    c=1;
    for(i=1;i<=C;i++)
        c*=10;
    int n = strlen(A);
    for(i = max(0, n - C - 1); i <= n - 1; i++)
    {
        a = a * 10 + A[i] - '0';
    }
    for(i=0; i<=15; i++)
    {
        for(int j=0; j<4; ++j)
        {
            if((i&(1<<j))>0)
            {
                b16[i][3-j]=1;
            }
        }
    }

    n=strlen(B);
    int t;
    for(i=0; i<n; i++)
    {
        if('0'<=B[i]&&B[i]<='9')
        {
            t=B[i]-'0';
        }
        else
        {
            t=10+B[i]-'A';
        }
        b[i*4  ] = b16[t][0];
        b[i*4+1] = b16[t][1];
        b[i*4+2] = b16[t][2];
        b[i*4+3] = b16[t][3];
    }
    /*for(i=0;i<4*n;i++)
    {
        printf("%d\n",b[i]);
    }*/
    MyType rez = functie(4 * n - 1);
    printf("%lld\n", rez.si);

    return 0;
}