/// Preset de infoarena
#include <fstream>

using namespace std;

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

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

int main()
{
    fin >> nr >> put >> c;
    mod = 1;
    for(int i = 1; i <= c; i++)
        mod *= 10;
    int val = 0, ind = 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[++ind] = (cif >> j) & 1;
    }
    for(int i = 1; i <= ind; i++)
    {
        ans = (1LL * ans * (sum + 1)) % mod;
        sum = (1LL * sum * sum) % mod;
        if(on[i])
        {
            sum = (1LL * sum * val) % mod;
            ans = (ans + sum) % mod;
        }
    }
    int aux = ans;
    while(aux * 10 < mod)
    {
        fout << 0;
        aux *= 10;
    }
    fout << ans;
    return 0;
}