#include <iostream>
#include <fstream>
#include <cmath>

#define int long long

using namespace std;

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

const int NMAX = 2e5;

bool b[NMAX + 1];

signed main(){

	string A;
	string B;

	fin >> A >> B;

	int c;

	fin >> c;

	c = pow(10, c);

	int a = 0;

	for(int i = max(0ll, (int)A.size() - c); i < (int)A.size(); i++)
		a = a * 10 + (A[i] - '0');

	int nrBits = 0;

	for(int i = 0; i <= (int)B.size() - 1; i++){
		int cif = 0;
		if('0' <= B[i] && B[i] <= '9')
			cif = B[i] - '0';
		else
			cif = B[i] - 'A' + 10;

		for(int j = 4; j >= 1; j--)
			b[++nrBits] = ((cif >> (j - 1)) & 1);
	}

	int ans = 0;
	int currSum = a;
	int currA = a;

	int sumA = 1;

	for(int i = 1; i <= nrBits; i++){

		ans = (ans * (sumA + 1)) % c;
		sumA = (sumA * sumA) % c;

		if(b[i]){
			(sumA *= a) %= c;
			(ans += sumA) %= c;
		}
	}

	c /= 10;

	while(ans < c && c > 0){
		c /= 10;
		fout << 0;
	}

	if(ans)
		fout << ans;

	/*int o = 1, sum = 0;
	for(int i = 1; i <= 9; i++){
		(o *= 124) %= 100000;
		(sum += o) %= 100000;
	}
	cout << sum;*/

	return 0;
}

// amusant: aceasta problema se poate si cu exponentiere de matrici:
// (Sn, An + 1) -> (Sn + 1, An + 2) cu ajutorul {(1, 0), (1, A)}