#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long


using namespace std;

ifstream in("calcul.in");
ofstream out("calcul.out");

ll A, MOD = 1, a;
int C;
char B[50005];
int b[50005];
int binCounter = 0;

void citire()
{
    in >> A;
    in >> B;
    in >> C;
}

void TakeMod(int x)
{
    for(int i = 1; i <= C; i++)
        MOD *= 10;
}

void TakeA()
{
    a = A%MOD;
}

void TakeB(char x[])
{
    int len = strlen(x);
    for(int i = 0; i < len; i++)
    {
        int hex;

        if(x[i] >= '0' && x[i] <= '9')
            hex = x[i] - '0';
        else hex = x[i] - 'A' + 10;

        for(int i = 3; i >= 0; i--)
        {
            if(hex & (1 << i))
            {
                b[binCounter++] = 1;
            }

            else
            {
                b[binCounter++] = 0;
            }
        }
    }
}

ll rez()
{
    ll result = 0;
    ll x = 1;

    for (int i = 0; i < binCounter; i++)
    {
        result = (result * (x + 1)) % MOD;
        x = (x * x) % MOD;

        if(b[i])
        {
            x = (x * a) % MOD;
            result = (result + x) % MOD;
        }
    }
    return result;
}

int main()
{
    citire();
    TakeMod(C);
    TakeA();
    TakeB(B);
    out << rez();
    return 0;
}