#include <cstdio>
#include <cstring>

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

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);
	l=strlen(sa);
	for (x=1, i=l-1; i>l-c && i>=0; i--, x*=10) 
		a+=x*(sa[i]-'0');
	l=strlen(sb);
	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)
	{
		printf("0");
		mod/=10;
	}
	printf("%lld\n",sum);
}