#include <bits/stdc++.h>
using namespace std;

string as, bs;
int a, c;
vector<bool> b;

long long MOD;

void read() {
	cin >> as >> bs >> c;
}

void computeMod() {
	MOD = 1;
	for (int i = 1; i <= c; i++)
		MOD *= 10;
}

void computeA() {
	for (int i = 0; i < as.size(); i++) {
		a = (a * 10 + as[i] - '0') % MOD;
	}
}

void computeB() {
	for (int i = 0; i < bs.size(); i++) {
		int hex;

		if(bs[i] >= '0' && bs[i] <= '9')
			hex = bs[i] - '0';
		else hex = bs[i] - 'A' + 10;

		for(int i = 3; i >= 0; i--) {
			if(hex & (1 << i)) {
				b.push_back(1);
			}

			else {
				b.push_back(0);
			}
		}
	}
}

int computeResult() {
	int result = 0;
	int x = 1;

	for (int i = 0; i < b.size(); i++) {
		result = (result * (x + 1)) % MOD;
		x = (x * x) % MOD;

		if(b[i]) {
			x = (x * a) % MOD;
			result = (result + x) % MOD;
		}
	}

	return result;
}

int main() {
	freopen("calcul.in", "r", stdin);
	freopen("calcul.out", "w", stdout);

	read();
	computeMod();
	computeA();
	computeB();
	
	cout << setfill('0') << setw(c) << computeResult();

	return 0;
}