#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char s[100002];
bool Bit[200001];
int c, a, MOD = 1 ,nrb=0,S=0;
void citire()
{
    int p = 1, n, cf, i;
    f >> s;
    n = strlen(s);
    n--;
    c = 0;
    while(n >= 0 && c <= 9)
    {
        a += (s[n--] - '0') * p;
        p *= 10;
        c++;
    }
    f >> s >> c;
    for(i = 1; i <= c; i++)MOD *= 10;
    a = a % MOD;
    for(int i = 0; s[i] != 0; i++)
    {
        if(s[i] <= 'A')cf = s[i] - '0';
        else cf = s[i] - 'A' + 10;
        for(int j = 3; j >= 0; j--)
            Bit[++nrb] = (cf >> j) & 1;
    }
}

void calcul()
{
    int P = 1;
    for(int i = 1; i <= nrb; i++)
    {
        S = 1LL * S * (1 + P) % MOD;
        P = 1LL * P * P % MOD;
        if(Bit[i])
        {
            P = 1LL * P * a % MOD;
            S = (S + P) % MOD;
        }
    }
}

int main()
{
    citire();
    calcul();
    g<<setw(c)<<setfill('0')<<S;
}