#include<stdio.h>
#include<cstring>

#define maxdim 100005

FILE*f=fopen("calcul.in","r");
FILE*g=fopen("calcul.out","w");

const int maxbiti = 500000;
int a,b,c,A,C,index;
char sirA[maxdim],B[maxdim>>1];
int phi[] = {0,4,40,400,4000,40000,400000,4000000,40000000,400000000};
int biti[maxbiti],lgpow[maxbiti],val[maxbiti];

void solve ( int niv ){
	if ( niv == index ){
		lgpow[niv] = val[niv] = A;
		return ;
	}
	
	solve(niv+1);
	
	if ( !biti[niv] ){
		lgpow[niv] = (1LL*lgpow[niv+1]*lgpow[niv+1])%C;
		val[niv] = (1LL*val[niv+1]*(lgpow[niv+1]+1))%C;
	}
	else{
		lgpow[niv] = (1LL*lgpow[niv+1]*lgpow[niv+1])%C;
		lgpow[niv] = (1LL*lgpow[niv]*A)%C;
		val[niv] = (1 + 1LL*val[niv+1]*(lgpow[niv+1]+1))%C;
		val[niv] = (1LL*A*val[niv])%C;
	}
}

int main () {
	
	fscanf(f,"%s%s%d",sirA+1,B+1,&c);
	a = strlen(sirA+1); b = strlen(B+1);
	
	for ( int i = a - c + 1 >= 1 ? a - c + 1 : 1 ; i <= a ; ++i ){
		A = A*10 + sirA[i]-'0';
	}
	
	C = 1;
	for ( int i = 1 ; i <= c ; ++i ){
		C *= 10;
	}
	
	for ( int i = b ; i >= 1 ; --i ){
		int N;
		if ( B[i] >= '0' && B[i] <= '9' ){
			N = B[i] - '0';
		}
		else{
			N = 10 + B[i] - 'A';
		}
		for ( int bit = 0 ; bit < 4 ; ++bit ){
			if ( N & (1<<bit) ){
				biti[++index] = 1;
			}
			else{
				biti[++index] = 0;
			}
		}
	}
	while ( !biti[index] )	--index;
	
	solve(1);
	
	C /= 10;
	while ( val[1] < C ){
		fprintf(g,"0");
		C /= 10;
	}
	fprintf(g,"%d\n",val[1]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}