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

using namespace std;

int a[N], b[N], c, sol[N], rez[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)
{
  memmove(&h[c+1],&h[1],sizeof(int)*h[0]);
  memset(&h[1],0,sizeof(int)*c);
  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]--;
}

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 rez[], int a[], int b[], int r[])
{
    int i;
    r[0]=0;rez[0]=a[0];
    for(i=a[0];i>0;i--)
    {
        shl(rez,1);r[1]=a[i];
        rez[i]=0;
        while(sgn(b,r)!=1)
        { rez[i]++;
          scadere(r,b);
        }
    }
    while(!rez[rez[0]] && rez[0]>1)
        rez[0]--;
}

void putere(int a[], int b[])
{
    if(b[0]==1 && b[1]==0)
        return;
    if(b[1]%2==0)
    {
        imultire(rez, a, a);
        for(int i=0;i<=rez[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]--;
        putere(a, b);
    }
    else
    {
        imultire(rez, sol, a);
        for(int i=0;i<=rez[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);

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