#include <cstdio>

char sa[100010], sb[50010], b[200010];
long long mod, a, sum, put;
int lb, c;

int main()
{
	freopen("calcul.in","r",stdin);
	freopen("calcul.out","w",stdout);
	int i, l;
	long long x;
	scanf("%s",sa);
	scanf("%s",sb);
	scanf("%d",&c);
	for (l=0; sa[l+1]; l++);
	l++;
	for (x=1, i=l-1; i>=l-c && i>=0; i--, x*=10) 
		a+=x*(sa[i]-'0');
	for (l=0; sb[l+1]; l++);
	l++;
	for (i=0; i<l; i++)
	{
		if (sb[i]>='A' && sb[i]<='Z') x=sb[i]-'A'+10; else
			x=sb[i]-'0';
		b[++lb] = x>>3;
		b[++lb] = (x>>2)&1;
		b[++lb] = (x>>1)&1;
		b[++lb] = x & 1;
	}
	for (mod=1, i=1; i<=c; i++) mod*=10;
	for (sum=0, put=1, i=1; i<=lb; i++)
	{
		sum= (sum*((1+put)%mod))%mod;
		put=(put*put)%mod;
		if (b[i]==1)
		{
			sum=(a*(1+sum)%mod)%mod;
			put=(put*a)%mod;
		}
	}
	mod/=10;
	while (sum<=mod && mod>1)
	{
		printf("0");
		mod/=10;
	}
	printf("%lld\n",sum);
}