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

#define maxdim 100005

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

int a,b,c;
char sirA[maxdim],B[maxdim>>1];
int phi[] = {0,4,40,400,4000,40000,400000,4000000,40000000,400000000};

int main () {
	
	fscanf(f,"%s%s%d",sirA+1,B+1,&c);
	a = strlen(sirA+1); b = strlen(B+1);
	
	int A = 0;
	for ( int i = a - c + 1 >= 1 ? a - c + 1 : 1 ; i <= a ; ++i ){
		A = A*10 + sirA[i]-'0';
	}
	
	int C = 1;
	for ( int i = 1 ; i <= c ; ++i ){
		C *= 10;
	}
	
	int s = 1,p = A;
	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';
		}
		
		while ( N ){
			if ( N & 1 ){
				s = (1LL*s*p) % C;
			}
			
			p = (1LL*p*p) % C;
			N >>= 1;
		}
	}
	
	int numarator = s - 1;
	if ( numarator < 0 )	numarator += C;
	numarator = (1LL*numarator * A) % C;
	
	--A; if ( A < 0 )	A += C;
	s = 1; p = A;
	
	int putere = phi[c]-1;
	while ( putere ){
		if ( putere & 1 ){
			s = (1LL*s*p) % C;
		}
		
		p = (1LL*p*p) % C;
		putere >>= 1;
	}
	
	int sol = (1LL*numarator*s) % C;
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}