#include <fstream>
#include <cstring>

using namespace std;

const char InFile[]="calcul.in";
const char OutFile[]="calcul.out";
const int MaxN=200111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,C,bit[MaxN],MOD;
char str[MaxN],str2[MaxN];
long long A,SOL[2][2],T[2][2];

int main()
{
	fin>>str;
	fin>>str2;
	fin>>C;
	fin.close();
	
	MOD=1;
	for(register int i=1;i<=C;++i)
	{
		MOD*=10;
	}
	
	int N=strlen(str);
	for(register int i=0;i<N;++i)
	{
		A*=10;
		A+=str[i]-'0';
		A%=MOD;
	}
	
	int ind=0;
	N=strlen(str2);
	for(register int i=N-1;i>=0;--i)
	{
		int val=str2[i]-'0';
		if('A'<=str2[i] && str2[i]<='Z')
		{
			val=10+str2[i]-'A';
		}
		for(register int k=0;k<4;++k)
		{
			bit[++ind]=val%2;
			val/=2;
		}
	}
	
	SOL[0][0]=1; SOL[0][1]=0;
	SOL[1][0]=0; SOL[1][1]=1;
	
	T[0][0]=A; T[0][1]=A;
	T[1][0]=0; T[1][1]=1;
	
	for(register int t=1;t<=ind;++t)
	{
		if(bit[t])
		{
			long long AUX[2][2];
			for(register int i=0;i<2;++i)
			{
				for(register int j=0;j<2;++j)
				{
					AUX[i][j]=0;
					for(register int k=0;k<2;++k)
					{
						AUX[i][j]+=SOL[i][k]*T[k][j];
						AUX[i][j]%=MOD;
					}
				}
			}
			for(register int i=0;i<2;++i)
			{
				for(register int j=0;j<2;++j)
				{
					SOL[i][j]=AUX[i][j];
				}
			}
		}
		long long AUX[2][2];
		for(register int i=0;i<2;++i)
		{
			for(register int j=0;j<2;++j)
			{
				AUX[i][j]=0;
				for(register int k=0;k<2;++k)
				{
					AUX[i][j]+=T[i][k]*T[k][j];
					AUX[i][j]%=MOD;
				}
			}
		}
		for(register int i=0;i<2;++i)
		{
			for(register int j=0;j<2;++j)
			{
				T[i][j]=AUX[i][j];
			}
		}
	}
	
	long long t=SOL[0][1];
	while(t<(MOD/10))
	{
		MOD/=10;
		fout<<"0";
	}
	if(SOL[0][1])
	{
		fout<<SOL[0][1];
	}
	fout.close();
	return 0;
}