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

#define maxdim 100005

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

const int maxbiti = 800000;
int a,b,c,A,C,INDEX;
char sirA[maxdim],B[maxdim>>1];
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;
	}
}

inline int cifre ( int x ){
	int c = 0;
	if ( !x )	return 1;
	while ( x ){
		++c;
		x /= 10;
	}
	return 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);
	
	int d = cifre(val[1]);
	for ( int i = d + 1 ; i <= c ; ++i ){
		fprintf(g,"0");
	}
	fprintf(g,"%d\n",val[1]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}