#include <cstdio>
#include <cstring>

using namespace std;

#define maxn 200010

int n, m, i, c, j, pt;
long long sol, a, mod, apt;
int bt[maxn];
char s[maxn], b[maxn];

int main()
{
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);

    scanf("%s%s%d", s, b, &c);

    pt=c;
    mod=1;
    for(int i=1; i<=c; ++i)
        mod=mod*10;

    n=strlen(s);
    for(int i=0; i<n; ++i)
        a=(1LL*a*10+s[i]-'0')%mod;

    n=strlen(b);
    for(int i=0; i<n; ++i)
    {
        if(b[i]>='A')
            c=10+b[i]-'A';
        else
            c=b[i]-'0';
        for(int j=3; j>=0; --j)
            bt[++m]=((c>>j)&1);
    }

    apt=1;

    for(int i=1; i<=m; ++i)
    {
        sol=sol*(1+apt)%mod;
        apt=(1LL*apt*apt)%mod;
        if(bt[i])
        {
            apt=(apt*a)%mod;
            sol=(sol+apt)%mod;
        }
    }

    for(int i=1; i<pt; ++i)
    {
        mod/=10;
        if(sol<mod)
            printf("0");
    }
    printf("%lld\n", sol);

    return 0;
}