#include <cstdio>
#include <cstring>

#define file_in "calcul.in"
#define file_out "calcul.out"

long long A,B,C,i,j,c,p,n,prod,x;
char s[1010000];

long long power(long long a, long long b)
{
	if (b==1)
		return a;
	if (b%2==0)
	{
		long long q;
		q=power(a,b/2);
		return q*q;
	}
	else
	{
		long long q;
		q=power(a,b/2);
		return q*q*a;
	}
}
	
	
int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%lld\n", &A);
	gets(s);
	scanf("%lld", &C);
	
	n=strlen(s);
	
	p=1;
	
	i=n-1;
	while(i>=0)
	{
		if (s[i]=='A') c=10;
		else
		if (s[i]=='B') c=11;
	    else
		if (s[i]=='C') c=12;
        else
		if (s[i]=='D') c=13;
		else
		if (s[i]=='E') c=14;
		else
		if (s[i]=='F') c=15;
        else
	        c=s[i]-'0';
		
		B+=(c*p);
		p*=16;
		i--;
	}
	
	//printf("%lld\n", B);
	
	prod=1;
	for (i=1;i<=C;++i) prod*=10;
	
	/*x=power(A,B+1);
	x-=A;
	x/=(A-1);*/
	x=0;
	
	for (i=1;i<=B;++i)
	{
		x=(x+power(A,i))%prod;
	}
		
		
	printf("%lld\n",x%prod);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}