#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 = (int)B.size() - 1; i >= 0; i--){
		int cif = 0;
		if('0' <= B[i] && B[i] <= '9')
			cif = B[i] - '0';
		else
			cif = B[i] - 'A' + 10;

		for(int j = 1; j <= 4; 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++){

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

		currSum = ((currSum * currA) % c + currSum) % c;
		currA = (currA * currA) % c;
	}

	c /= 10;

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

	if(ans)
		fout << ans;

	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)}