#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("calcul.in");
ofstream g ("calcul.out");
long long inm[3][3], aux[3][3], rez[3][3], MOD, bt[200001], p;
int c;
string a, b;

int main ()
{
    f >> a >> b >> c;
    MOD = 1;
    for (int i = 1; i <= c; i++)
        MOD *= 10;
    for(int i = max(0, (int)a.size() - c); i < a.size(); i++)
		p = p * 10 + (a[i] - '0') * 1LL;
    int biti = 0;
    for (int i = b.size() - 1; i >= 0; i--) {
        int nr = isdigit(b[i]) ? b[i] - '0' : b[i] - 'A' + 10;
        for (int j = 1; j <= 4; j++)
            bt[++biti] = ((nr >> (j - 1)) & 1);
    }
    long long ans = 0, sumcurr = p, acurr = p, suma = 1;
    for (int i = 1; i <= biti; i++) {
        if (bt[i])
        {
            ans = (ans + sumcurr * suma) % MOD;
            suma = (suma * acurr) % MOD;
        }
        sumcurr = (sumcurr * acurr + sumcurr) % MOD;
        acurr = (acurr * acurr) % MOD;
    }
    MOD /= 10;
    while (ans < MOD && MOD > 0) {
        MOD /= 10;
        g << 0;
    }
    if (ans > 0)
        g << ans;
    return 0;
}