#include <fstream>
#include <iostream>

#define MAX 200005

using namespace std;

string sA, sB;
int A, C, MOD, ans;
int B[MAX], nrBit;

void citire() {
	ifstream in("calcul.in");
	in>>sA>>sB>>C;
	in.close();
}

void solve() {
	/* getting 10^C */
	int MOD = 1;
	for(int i = 1; i <= C; i++) MOD *= 10;
	/* getting A */
	for(size_t i = 0; i < sA.size(); i++) A = (1LL * A * 10 + sA[i] - '0') % MOD;
	/* getting binary representation of B */
	for(int i = sB.size() - 1, digit; i >= 0; i--) {
		if(isdigit(sB[i])) digit = sB[i] - '0';
		else digit = 10 + sB[i] - 'A';
		for(int bit = 0; bit < 4; bit++) {
			B[++nrBit] = digit & 1;
			digit >>= 1;
			cerr<< B[nrBit] << " ";
		}
	} cerr<<"\n";
	/* removing starting zeroes */
	for(; !B[nrBit]; nrBit--);
	/* getting the last C digits of sum(A^k) */
	ans = A; // last C digits of A^1
	int put = A; // the power of the last member in the sequence considered
	for(int i = nrBit - 1; i; i--) {
		//cerr<<i<<" "<<ans<<" "<<put<<"\n";
		ans = (1LL * ans + 1LL * ans * put) % MOD;
		put = (1LL * put * put) % MOD;
		if(B[i]) {
			ans = (1LL * ans + 1LL * put * A) % MOD;
			put = (1LL * put * A) % MOD;
		}
	}	 
}

void afisare() {
	ofstream out("calcul.out");
	out << ans <<"\n";
	out.close();
}

int main() {
	citire();
	solve();
	afisare();
}