#include <fstream>
#include <cstring>
#define DIM 200010
using namespace std;
ifstream fin ("calcul.in");
ofstream fout ("calcul.out");
int nr,n,x,sol,A,i,c,MOD,val,p,ok;
long long sol2;
int a[DIM],b[DIM];
char s[DIM];
void trans_bit (int x){
for (int i=3;i>=0;i--)
b[++b[0]] = (x>>i)&1;
}
int get_rest (int a[],int b){
int r = 0;
for (int i=n;i;i--)
r = (r*10+a[i])%b;
return r;
}
int main (){
fin>>s+1;
nr = strlen (s+1);
for (i=1;i<=nr;i++)
a[i] = s[i] - '0';
a[0] = nr;
fin>>s+1;
nr = strlen (s+1);
for (i=1;i<=nr;i++){
if (s[i] >= '0' && s[i] <= '9')
trans_bit (s[i]-'0');
else trans_bit (s[i]-'A'+10);
}
fin>>c;
MOD = 1;
for (i=1;i<=c;i++)
MOD *= 10;
A = 0;
for (i=max(a[0]-c+1,1);i<=a[0];i++)
A = A*10 + a[i];
//A = get_rest (a,MOD);
sol = 0, val = 1;
for (i=1;i<=b[0];i++){
/// a b/2
if (b[i] == 0){
sol = (1LL*sol*(1+val))%MOD;
val = (1LL*val*val)%MOD;
}
else {
sol = (1LL*sol*(1+val))%MOD;
val = (1LL*val*val)%MOD;
sol = (1LL*sol*A + A)%MOD;
val = (1LL*val*A)%MOD;
}
}
sol %= MOD;
p = MOD / 10;
while (p != 1){
if (sol < p)
fout<<0;
p /= 10;
}
fout<<sol;
return 0;
}