#include <bits/stdc++.h>

using namespace std;
ifstream r("calcul.in");
ofstream w("calcul.out");

string nr, put;
int c, mod, mat[2][2], aux[2][2], on[200005], rez, sum = 1;

int main()
{
    r >> nr >> put >> c;
    mod = 1;
    for(int i = 1; i <= c; i++)
    {
        mod *= 10;
    }
    int val = 0, a = 0, n = nr.size();
    for(int i = max(n - c, 0); i < n; i++)
    {
        val = val * 10 + (nr[i] - '0');
    }
    for(int i = 0; i < put.size(); i++)
    {
        int cif = put[i] - '0';
        if(put[i] >= 'A')
        {
            cif = put[i] - 'A' + 10;
        }
        for(int j = 3; j >= 0; j--)
        {
            on[++a] = (cif >> j) & 1;
        }
    }
    for(int i = 1; i <= a; i++)
    {
        rez = (1LL * rez * (sum + 1)) % mod;
        sum = (1LL * sum * sum) % mod;
        if(on[i])
        {
            sum = (1LL * sum * val) % mod;
            rez = (rez + sum) % mod;
        }
    }
    mod /= 10;
    while(mod && rez < mod)
    {
        mod /= 10;
        w << 0;
    }
    if(rez)
    {
        w << rez;
    }
    return 0;
}