#include <cstring>
#include <cstdio>
#define N 500005

using namespace std;

int a[N], b[N], c, sol[N], rez[N], aux[N];
char nr[N];

void imultire(int rez[], int a[], int b[])
{
    int i, j, t=0;
    rez[0]=a[0]+b[0]-1;
    for(i=1;i<=a[0]+b[0];i++)
        rez[i]=0;
    for(i=1;i<=a[0];i++)
        for(j=1;j<=b[0];j++)
            rez[i+j-1]+=a[i]*b[j];
    for(i=1;i<=rez[0];i++)
    {
        rez[i]+=t;
        t=rez[i]/10;
        rez[i]%=10;
    }
    if(t)
        rez[++rez[0]]=t;
}

void shl(int h[], int c)
{
    int i;
    for(i=h[0];i;i--)
        h[i+c]=h[i];
    for(i=1;i<=c;)
        h[i++]=0;
    h[0]+=c;
}

void scadere(int a[], int b[])
{
    int i, t=0;
    for(i=b[0]+1;i<=a[0];i++)
        b[i]=0;
    for(i=1;i<=a[0];i++)
    {
        a[i]=a[i]-(b[i]+t);
        if(a[i]<0)
            t=1;
        else
            t=0;
        if(t)
            a[i]+=10;
       }
    while(!a[a[0]] && a[0]>1)
        a[0]--;
}

int sgn(int h1[], int h2[])
{
    while(h1[0] && !h1[h1[0]])
        h1[0]--;
    while(h2[0] && !h2[h2[0]])
            h2[0]--;
    if(h1[0]<h2[0])
        return -1;
    else
        if(h1[0]>h2[0])
            return +1;
    for(int i=h1[0];i>0;i--)
        if(h1[i]<h2[i])
            return -1;
        else
            if(h1[i]>h2[i])
                return 1;
    return 0;
}

void impartire(int a[], int b[], int c[], int r[])
{
    int i;
    r[0]=0;c[0]=a[0];
    for(i=a[0];i;i--)
    {
        shl(r, 1);
        r[1]=a[i];
        c[i]=0;
        while(sgn(b,r)!=1)
        {
            c[i]++;
            scadere(r,b);
        }
    }
    while(!c[c[0]] && c[0]>1)
        c[0]--;
}

void putere(int a[], int b[])
{
    if(b[0]==1 && b[1]==1)
    {
        if(sol[0]==0)
        {
            for(int i=0;i<=a[0];i++)
                sol[i]=a[i];
        }
        return;
    }
    if(b[1]%2==0)
    {
        imultire(rez, a, a);
        for(int i=rez[0];i>=0;i--)
            a[i]=rez[i];
        int r=0;
        for(int i=b[0];i>=1;i--)
        {
            int aux=b[i]+r;
            b[i]=(b[i]+r)/2;
            r=aux%2;
        }
        while(b[b[0]]==0  && b[0]>1)
            b[0]--;
        putere(a, b);
    }
    else
    {
        imultire(rez, sol, a);
        for(int i=rez[0];i>=0;i--)
            sol[i]=rez[i];
        int j=1;
        while(b[j]==0)
        {
            b[j]=9;
            j--;
        }
        b[j]--;
        if(j==b[0])
            b[0]--;
        putere(a, b);
    }
}

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

    fgets(nr, N, stdin);
    int i;
    for(i=strlen(nr)-1;i>=1;i--)
        a[i]=rez[i]=nr[i-1]-'0';
    a[0]=strlen(nr)-1;
    fgets(nr, N, stdin);
    for(i=strlen(nr)-1;i>=1;i--)
    {
        if(nr[i-1]>='0' && nr[i-1]<='9')
            b[i]=nr[i-1]-'0';
        else
            b[i]=nr[i-1]-'A'+10;
    }
    b[0]=strlen(nr)-1;
    b[1]++;
    scanf("%d", &c);

    for(int i=0;i<=a[0];i++)
        aux[i]=a[i];
    putere(aux, b);
    scadere(sol, a);
    a[1]--;
    impartire(sol, a, rez, b);
    for(i=c;i>0;i--)
        printf("%d", rez[i]);
    return 0;
}