#include <fstream>
#include <cstring>

using namespace std;

typedef long long ll;
const int NMAX = 1e5 + 1;

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

char a[NMAX], b[NMAX];
int c, nrb, lg, lg2, crt;
ll bit[2 * NMAX], b2, mod, sol, scrt, acrt, s;

int main()
{
    fin >> a >> b >> c;
    for(int i = 1; i <= c; i++) mod *= 10;
    lg = strlen(a), lg2 = strlen(b);
    for(int i = max(lg - c, 0); i < lg; i++) b2 = b2 * 10 + (a[i] - '0') * 1LL;
    for(int i = lg2 - 1; i >= 0; i--)
    {
        crt = isdigit(b[i]) ? b[i] - '0' : b[i] - 'A' + 10;
        for(int j = 1; j <= 4; j++) bit[++nrb] = ((crt >> (j - 1)) & 1);
    }
    sol = 0, scrt = b2, acrt = b2, s = 1;
    for(int i = 1; i <= nrb; i++)
    {
        if(bit[i])
        {
            sol = (sol + scrt * s) % mod;
            s = (s * acrt) % mod;
        }
        scrt = (scrt * acrt + scrt) % mod;
        acrt = (acrt * acrt) % mod;
    }
    mod /= 10;
    while(sol < mod && mod > 0)
    {
        mod /= 10;
        fout << 0;
    }
    if(sol > 0) fout << sol;
    return 0;
}