#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

string a, b;
long long int C, MOD = 1, A, P = 1, D;
vector<int> B;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> a;
    fin >> b;
    fin >> C;
    int it = a.size()-1;
    int CC = C;
    while (CC--)
    {
        char x = '0';
        if (it >= 0)
            x = a[it];
        A+=MOD*(x-'0');
        it--;
        MOD*=10;
    }
    for (int i = 0; i < b.size(); i++)
    {
        int x;
        if ('A' <= b[i])
            x = b[i]-'A'+10;
        else
            x = b[i]-'0';
        for (int j = 3; j >= 0; j--)
            B.push_back((x>>j)&1);
    }
    for (int i = 0; i < B.size(); i++)
    {
        D = (D*(P+1))%MOD;
        P = (P*P)%MOD;
        if (B[i])
        {
            P = (P*A)%MOD;
            D = (D+P)%MOD;
        }
    }
    int cD = D, cnt = 0;
    while (cD)
    {
        cnt++;
        cD/=10;
    }
    if (D == 0)
        cnt = 1;
    for (int i = cnt; i < C; i++)
        fout << 0;
    fout << D;
    return 0;
}