#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
int n, m, c, mod, a, b, ans[2][2], mat[2][2], sum, ps[maxN];
char s2[maxN], s1[maxN];
vector < int > v;
void mul(int a[2][2], int b[2][2])
{
    int i, j, k, res[2][2];
    for (i = 0; i < 2; ++ i)
        for (j = 0; j < 2; ++ j)
        {
            res[i][j] = 0;
            for (k = 0; k < 2; ++ k)
                res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
        }

    memcpy(a, res, sizeof(res));
}
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 = 0; i < m; ++ i)
    {
        int b, j;
        if (s2[i] >= '0' && s2[i] <= '9')
            b = s2[i] - '0';
        else
            b = s2[i] - 'A' + 10;
        for (j = 0; j < 4; ++ j)
            v.push_back(b & (1 << j));
    }

    ans[0][1] = ans[1][1] = mat[1][1] = 1;
    mat[0][0] = mat[1][0] = a;
    for (i = 0; i < v.size(); ++ i)
    {
        if (v[i])
            mul(ans, mat);
        mul(mat, mat);
    }

}
void write()
{
    int i;
    freopen("calcul.out", "w", stdout);
    printf("%d\n", ans[0][0]);
    /*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;
}