# include <bits/stdc++.h>
using namespace std;
ifstream fi("calcul.in");
ofstream fo("calcul.out");
# define ll long long
# define ull unsigned long long
// bignumber
const int base = 10;
struct big
{
char d[100005];
int n;
big()
{
n = 0;
memset(d,0,sizeof(d));
}
};
big trans(int b)
{
big ans;
while (b) ans.d[++ans.n] = b%base,b /= base;
return ans;
}
void print(big a)
{
for (int i = a.n;i;--i) fo << int(a.d[i]);
fo << '\n';
}
bool operator < (big a,big b)
{
if (a.n != b.n) return a.n < b.n;
for (int i = a.n;i;--i) if (a.d[i] != b.d[i]) return (a.d[i] < b.d[i]);
return 0;
}
bool operator > (big a,big b)
{
if (a.n != b.n) return a.n > b.n;
for (int i = a.n;i;--i) if (a.d[i] != b.d[i]) return (a.d[i] > b.d[i]);
return 0;
}
bool operator == (big a,big b)
{
if (a.n != b.n) return 0;
for (int i = a.n;i;--i) if (a.d[i] != b.d[i]) return 0;
return 1;
}
bool operator <= (big a,big b)
{
if (a.n != b.n) return a.n < b.n;
for (int i = a.n;i;--i) if (a.d[i] != b.d[i]) return (a.d[i] < b.d[i]);
return 1;
}
bool operator >= (big a,big b)
{
if (a.n != b.n) return a.n > b.n;
for (int i = a.n;i;--i) if (a.d[i] != b.d[i]) return (a.d[i] > b.d[i]);
return 1;
}
void operator += (big& a,int b)
{
a.d[1] += b;
int cnt = 1;
while (a.d[cnt] >= base)
{
a.d[cnt+1] += a.d[cnt] / base;
a.d[cnt] %= base;
++cnt;
}
a.n = max(a.n,cnt);
}
void operator -= (big& a,int b)
{
int t = 0;
for (int i = 1;i <= a.n || t || b;++i)
{
a.d[i] -= b % base + t;
a.d[i] += base * (t = a.d[i] < 0);
b /= base;
}
while (!a.d[a.n] && a.n) --a.n;
}
void operator ++ (big& a)
{
a += 1;
}
void operator -- (big& a)
{
a -= 1;
}
void operator += (big& a,big b)
{
int t = 0,to = max(a.n,b.n),i;
for (i = 1;i <= to || t;++i)
{
t += a.d[i] + b.d[i];
a.d[i] = t%base;
t /= base;
}
a.n = i - 1;
}
void operator -= (big& a,big b)
{
int i,t = 0;
for (i = 1;i <= a.n;++i)
{
a.d[i] -= (i <= b.n ? b.d[i]:0) + t;
a.d[i] += (t = a.d[i] < 0) * base;
}
while (!a.d[a.n] && a.n) --a.n;
}
void operator *= (big& a,big b)
{
int i,j,t;
big c;
for (i = 1;i <= a.n;++i)
{
for (t = 0,j = 1;j <= b.n || t;++j)
{
t += c.d[i + j - 1] + a.d[i] * b.d[j];
c.d[i + j - 1] = t%base;
t /= base;
}
if (i + j - 2 > c.n) c.n = i + j - 2;
}
a = c;
}
big operator * (big a,big b)
{
big c;
c.n = 1;
c.d[1] = 1;
c *= a;
c *= b;
return c;
}
big operator + (big a,big b)
{
big c;
c += a;
c += b;
return c;
}
big operator - (big a,big b)
{
big c = a;
c -= b;
return c;
}
int operator %(big a,int b)
{
int i,t = 0;
for (i = a.n;i;--i) t = (t * base + a.d[i]) % b;
return t;
}
void down(big& a,int b)
{
for (int i = 1;i <= a.n - b;++i) a.d[i] = a.d[i+b];
for (int i = a.n-b+1;i<=a.n;++i) a.d[i] = 0;
a.n -= b;
}
void up(big& a,int b)
{
for (int i = a.n+b;i >= b+1;--i) a.d[i] = a.d[i-b];
for (int i = 1;i <= b;++i) a.d[i] = 0;
a.n += b;
}
void operator %= (big& a,big b)
{
big c;
for (int i = a.n;i;--i)
{
up(c,1);
c.d[1] = a.d[i];
while (c >= b) c -= b;
}
a = c;
}
big operator % (big a,big b)
{
big c = a;
c %= b;
return c;
}
void operator *= (big& a,int b)
{
int i,t = 0;
for (i = 1;i <= a.n || t;++i)
{
t += a.d[i] * b;
a.d[i] = t%base;
t /= base;
}
a.n = i - 1;
}
big operator * (big a,int b)
{
big c = a;
c *= b;
return c;
}
void operator /= (big& a,int b)
{
int t = 0;
for (int i = a.n;i;--i)
{
t = t * base + a.d[i];
a.d[i] = t / b;
t %= b;
}
while (!a.d[a.n] && a.n) --a.n;
}
big operator / (big a,int b)
{
big c = a;
c /= b;
return c;
}
void operator /= (big& a,big b)
{
big c,ans;
for (int i = a.n;i;--i)
{
up(c,1);
c.d[1] = a.d[i];
while (c >= b) ++ans.d[i],c -= b;
}
ans.n = a.n;
while (!ans.d[ans.n] && ans.n) --ans.n;
a = ans;
}
big operator / (big a,big b)
{
big c = a;
c /= b;
return c;
}
big pw(big a,int b)
{
big ans = trans(1);
while (b)
{
if (b&1) ans *= a;
a = a * a;
b >>= 1;
}
return ans;
}
big f(big a,int c)
{
return a < trans(c) ? trans(0): a / c + f(a / c,c);
}
// end bignumber
// pairs
struct pdd
{
double x,y;
pdd()
{
x = y = 0;
}
};
struct pddi
{
double x,y;
int z;
pddi()
{
x = y = 0;
z = 0;
}
};
struct pii
{
int x,y;
pii()
{
x = y = 0;
}
};
struct pil
{
int x;
ll y;
pil()
{
x = y = 0;
}
};
struct pll
{
ll x,y;
pll()
{
x = y = 0;
}
};
struct piii
{
int x,y,z;
piii()
{
x = y = z = 0;
}
};
struct piil
{
int x,y;
ll z;
piil()
{
x = y = z = 0;
}
};
struct pill
{
int x;
ll y,z;
pill()
{
x = y = z = 0;
}
};
struct plll
{
ll x,y,z;
plll()
{
x = y = z;
}
};
bool operator < (pii a,pii b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool operator > (pii a,pii b)
{
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
bool operator <= (pii a,pii b)
{
if (a.x == b.x) return a.y <= b.y;
return a.x <= b.x;
}
bool operator >= (pii a,pii b)
{
if (a.x == b.x) return a.y >= b.y;
return a.x >= b.x;
}
bool operator < (pdd a,pdd b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool operator > (pdd a,pdd b)
{
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
bool operator <= (pdd a,pdd b)
{
if (a.x == b.x) return a.y <= b.y;
return a.x <= b.x;
}
bool operator >= (pdd a,pdd b)
{
if (a.x == b.x) return a.y >= b.y;
return a.x >= b.x;
}
bool operator < (pddi a,pddi b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
}
bool operator > (pddi a,pddi b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z > b.z;
return a.y > b.y;
}
return a.x > b.x;
}
bool operator <= (pddi a,pddi b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z <= b.z;
return a.y <= b.y;
}
return a.x <= b.x;
}
bool operator >= (pddi a,pddi b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z >= b.z;
return a.y >= b.y;
}
return a.x >= b.x;
}
bool operator < (pil a,pil b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool operator > (pil a,pil b)
{
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
bool operator <= (pil a,pil b)
{
if (a.x == b.x) return a.y <= b.y;
return a.x <= b.x;
}
bool operator >= (pil a,pil b)
{
if (a.x == b.x) return a.y >= b.y;
return a.x >= b.x;
}
bool operator < (pll a,pll b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool operator > (pll a,pll b)
{
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
bool operator <= (pll a,pll b)
{
if (a.x == b.x) return a.y <= b.y;
return a.x <= b.x;
}
bool operator >= (pll a,pll b)
{
if (a.x == b.x) return a.y >= b.y;
return a.x >= b.x;
}
bool operator < (piii a,piii b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
}
bool operator > (piii a,piii b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z > b.z;
return a.y > b.y;
}
return a.x > b.x;
}
bool operator <= (piii a,piii b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z <= b.z;
return a.y <= b.y;
}
return a.x <= b.x;
}
bool operator >= (piii a,piii b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z >= b.z;
return a.y >= b.y;
}
return a.x >= b.x;
}
bool operator < (piil a,piil b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
}
bool operator > (piil a,piil b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z > b.z;
return a.y > b.y;
}
return a.x > b.x;
}
bool operator <= (piil a,piil b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z <= b.z;
return a.y <= b.y;
}
return a.x <= b.x;
}
bool operator >= (piil a,piil b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z >= b.z;
return a.y >= b.y;
}
return a.x >= b.x;
}
bool operator < (pill a,pill b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
}
bool operator > (pill a,pill b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z > b.z;
return a.y > b.y;
}
return a.x > b.x;
}
bool operator <= (pill a,pill b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z <= b.z;
return a.y <= b.y;
}
return a.x <= b.x;
}
bool operator >= (pill a,pill b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z >= b.z;
return a.y >= b.y;
}
return a.x >= b.x;
}
bool operator < (plll a,plll b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
}
bool operator > (plll a,plll b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z > b.z;
return a.y > b.y;
}
return a.x > b.x;
}
bool operator <= (plll a,plll b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z <= b.z;
return a.y <= b.y;
}
return a.x <= b.x;
}
bool operator >= (plll a,plll b)
{
if (a.x == b.x)
{
if (a.y == b.y) return a.z >= b.z;
return a.y >= b.y;
}
return a.x >= b.x;
}
//end pair
// functii
ll pw(ll a,ll b,ll mod)
{
int ans = 1;
while (b)
{
if (b&1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int f(ll a,ll b)
{
return a < b ? 0:a/b + f(a/b,b);
}
int gcd(int a,int b)
{
return b ? a:gcd(a,b);
}
ll gcd(ll a,ll b)
{
return b ? a:gcd(a,b);
}
ll lcm(ll a,ll b)
{
return 1ll * a * b / gcd(a,b);
}
int phi(int n)
{
int cnt = n,p = n,ans = n;
for (int i = 2;i*i <= p;++i)
if (!(cnt%i))
{
ans /= i;ans *= (i-1);
while (!(cnt%i)) cnt /= i;
}
if (cnt > 1) ans /= cnt,ans *= (cnt - 1);
return ans;
}
//end functii
int s[256];
char t[100005];
char a[100005];
bitset < 800005 > ok;
int main(void)
{
for (int i = 'A';i <= 'F';++i) s[i] = i - 'A' + 10;
for (int i = '0';i <= '9';++i) s[i] = i - '0';
fi>>(a+1);
ll newa = 0;
fi>>(t+1);
int c;
fi>>c;
int len = strlen(a+1);
for (int i = max(1,len - c + 1);i <= len;++i) newa = newa * 10 + a[i] - '0';
int lg = c;
c = pw(10,c,(ll)(1e16));
int cn = 0;
for (int i = strlen(t+1);i;--i)
{
int k = s[t[i]];
for (int cnt = 0;cnt < 4;++cnt) ok[++cn] = k&1,k >>= 1;
}
while (cn && !ok[cn]) --cn;
ll put = 1;
ll ans = 0;
for (int i = cn;i;--i)
{
ans = (1ll * ans * (put + 1))%c;
if (ok[i]&1) ans = (1ll * newa * (1 + ans)) % c;
put = (put * put) % c;
if (ok[i]) put *= newa,put %= c;
}
ans %= c;
int l = 0;
ll pl = ans;
while (pl) ++l,pl /= 10;
l = lg - l;
while (l --) fo << "0";
return fo << ans << '\n',0;
}