#include<fstream>
#include<map>

using namespace std;
typedef int64_t var;

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

map<char, var> COD;
var MOD;
var euler;

inline var putere(var b, var e) {
    if(e==0) return 1;
    if(e%2==0) return putere((b*b)%MOD, e/2);
    return (b* putere(b, e-1))%MOD;
}

inline var inv(var c) {
    return putere(c, euler - 1);
}

string A, B;
var a, b;

int main() {
    var c;
    fin>>A>>B>>c;
    MOD = 1;

    for(var i=1; i<=c; i++) MOD*=10;
    euler = MOD /2 * 4/5;

    for(var i=0; i<10; i++) COD[i+'0'] = i;
    for(var i=0; i<6; i++) COD[i+'A'] = i+10;

    for(var i=max(0LL, A.length() - c); i<A.length(); i++) {
        a = a*10 + A[i] - '0';
    }
    for(var i=0; i<B.length(); i++) {
        b = b*16 + COD[B[i]];
        b %= MOD;
    }


    fout<<((putere(a, b+1) + MOD - 1)*inv((a+MOD-1)%MOD) + MOD-1)%MOD;

}