#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
int n, m, c, mod, a, b, ans, sum, ps[maxN];
char s2[maxN], s1[maxN];
void read()
{
freopen("calcul.in", "r", stdin);
fgets(s1, maxN, stdin);
n = strlen(s1) - 1;
fgets(s2, maxN, stdin);
m = strlen(s2) - 1;
scanf("%d", &c);
}
int lgput(int a, int b)
{
if (b == 0)
return 1;
if (b == 1)
return a;
if (b % 2 == 0)
{
return lgput((1LL * a * a) % mod, b / 2);
}
return (1LL * a * lgput(a, b - 1)) % mod;
}
int Psum(int b)
{
int i, j, powa = a, B, sum = 0;
ps[0] = a;
for (i = 1; (1 << i) <= b; ++ i)
{
ps[i] = (1LL * ps[i - 1] * (powa + 1)) % mod;
powa = (1LL * powa * powa) % mod;
}
sum = ps[i - 1];
B = (1 << (i - 1)) + 1;
for (j = 0; j < i - 1; ++ j)
if (b & (1 << j))
{
sum = (sum + 1LL * ps[j] * lgput(a, B - 1)) % mod;
B += (1 << j);
}
return sum;
}
void solve()
{
int i;
mod = 1;
for (i = 1; i <= c; ++ i)
mod *= 10;
for (i = 0; i < n; ++ i)
a = (a * 10 + (s1[i] - '0')) % mod;
for (i = m - 1; i >= 0; -- i)
{
if (s2[i] >= '0' && s2[i] <= '9')
b = (b * 16 + (s2[i] - '0')) % (mod - 1);
else
b = (b * 16 + 10 + (s2[i] - 'A')) % (mod - 1);
}
ans = Psum(b);
}
void write()
{
int i;
freopen("calcul.out", "w", stdout);
printf("%d\n", ans);
/*sum = 0;
for (i = 1; i <= b; ++ i)
sum = (1LL * sum + 1LL * lgput(a, i)) % mod;
printf("%d\n", sum);*/
}
int main()
{
read();
solve();
write();
return 0;
}