#include <fstream>
#include <iomanip>

#define MAX 200005

using namespace std;

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

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;
		}
	} 
	/* removing starting zeroes */
	for(; !B[nrBit]; nrBit--);
	/* getting the last C digits of sum(A^k) */
	ans = A; // last C digits of A^1
	long long put = A; // the power of the last member in the sequence considered
	for(int i = nrBit - 1; i; i--) {
		ans += ans * put;
		put *= put;
		if(ans >= MOD) ans %= MOD;
		if(put >= MOD) put %= MOD;
		if(B[i]) {
			ans += (put *= A);
			if(ans >= MOD) ans %= MOD;
			if(put >= MOD) put %= MOD;
		}
	}	 
}

void afisare() {
	ofstream out("calcul.out");
	out << setfill('0') << setw(C) << ans <<"\n";
	out.close();
}

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