# 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);
    int newa = 0;
    fi>>(t+1);
    int c;
    fi>>c;
    for (int i = 1;i <= min(c,(int)strlen(a+1));++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;
    }
    int l = 0,pl = ans;
    while (pl) ++l,pl /= 10;
    l = lg - l;
    while (l --) fo << "0";
    return fo << ans << '\n',0;
}