#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;

/*

calcul x 0 = 1
calcul x (2y) = (1 + x ^ y) * calcul x y
calcul x (2y+1) = 1 + x * (1 + x ^ y) * calcul x y

astfel "calcul" foloseste doar puteri de x ce corespund unor prefixe al lui y

*/

using ll = long long;
constexpr ll maxb = 200000 + 10;

ll a = 0, c;
bitset<maxb> b;
ll blen;
ll mod;

int main(){
    {
    ifstream f("calcul.in");
    string sa, sb;
    f >> sa >> sb >> c;
    mod = pow(10, c);

    for(ll i = 0; i < sa.size(); ++i)
        a = (10ll * a + sa[i] - '0') % mod;

    blen = 4 * sb.size();
    for(ll i = 0, j = 0; i < sb.size(); ++i, j += 4){
        ll val = (isdigit(sb[i]) ? sb[i] - '0' : sb[i] - 'A' + 10);
        for(ll k = j+3; k >= j; --k)
            b[k] = val%2, val /= 2; }
    }
    a %= mod;

    ll curr = 0;
    for(ll i = 0, pref_power = 1; i < blen; ++i){
        curr = (curr * (1 + pref_power))%mod;
        if(b[i]) curr = (curr * a + 1) % mod;
        pref_power = (pref_power * pref_power) % mod;
        if(b[i]) pref_power = (pref_power * a) % mod; }


    ofstream g("calcul.out");
    g.width(c);
    g.fill('0');
    g << (curr * a) % mod << endl;
    return 0; }