#include <iostream>
#include <fstream>
#include <string>
#include <bitset>

using namespace std;

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

typedef long long lint;

lint a = 0, c = 1;
bitset<200041> b;
struct mam{
	lint x[5][5];
	mam(){
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				x[i][j] = 0;
			}
		}
	}
	void sugma(){
		x[0][0] = 1;
		x[1][0] = x[1][1] = a;
	}
	void ligma(){
		x[0][0] = x[1][1] = 1;
	}
	mam mul(mam & rhs){
		mam r;
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				for(int k = 0; k < 2; k++){
					r.x[i][j] += x[i][k]*rhs.x[k][j];
					r.x[i][j] %= c;
				}
			}
		}
		return r;
	}
	void deb(){
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				cout << x[i][j] << "\t";
			}
			cout << "\n";
		}
	}
};

int tanaca(char c){
	return c-'0';
}

int tanaba(char c){
	if(c >= '0' && c <= '9'){
		return c-'0';
	}else{
		return c-'A'+10;
	}
}

void readit(){
	string sa, sb;
	int dc;
	fin >> sa >> sb >> dc;
	for(int i = 1; i <= dc; i++){
		if(i <= sa.size()){
			a += tanaca(sa[sa.size()-i]) * c;
		}
		c *= 10;
	}
	
	int baka = 0, xoxo;
	for(int i = sb.size()-1; i >= 0; i--){
		xoxo = tanaba(sb[i]);
		for(int j = baka; j < baka+4; j++){
			b[j] = xoxo&1;
			xoxo >>= 1;
		}
		baka += 4;
	}
}

void mentos(int a){
	c /= 10;
	while(a <= c){
		fout << 0;
		c /= 10;
	}
	fout << a;
}

void solveit(){
	mam r, p;
	r.ligma();p.sugma();
	for(int i = 0; i < 200000; i++){
		if(b[i]){
			r = r.mul(p);
		}
		p = p.mul(p);
	}
	mentos(r.x[1][0]);
}

int main(){
	readit();
	solveit();
}