#include <cstdio>
#include <cstring>

using namespace std;

char nrA[100005], b[500005];
int c, MOD=1, a, l, lb, mat[2][2], rez[2][2];

void modul()
{
    for(int i=1; i<=c; i++)
        MOD*=10;
}

void calcA()
{
    int panaUnde=0;
    if(l>c)
        panaUnde=l-c;
    for(int i=panaUnde; i<l; i++)
        a=a*10+(nrA[i]-'0');
}

void formMat()
{
    mat[0][0]=1;
    mat[1][0]=a;
    mat[1][1]=a;
}

void inmultire(int m1[2][2], int m2[2][2], int rez[2][2])
{
    int temp[2][2]={{0, 0}, {0, 0}};
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                temp[i][j]=(temp[i][j]+(1LL*m1[i][k]*m2[k][j])%MOD)%MOD;

    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            rez[i][j]=temp[i][j];
}

int hexDig(char x)
{
    if(x>='0' && x<='9')
        return x-'0';
    return x-'A'+10;
}


void ridica(int M[2][2], int rez[2][2])
{
    rez[0][0]=rez[1][1]=1;
    rez[0][1]=rez[1][0]=0;
    int ind=0;
    for(int i = lb-1; i >= 0; i--)
    {
        int cif=hexDig(b[i]);
        for(int ind=0; ind<4; ind++)
        {
            int bit = ((cif >> ind)&1);
            if(bit)
                inmultire(rez, M, rez);
            inmultire(M, M, M);

        }
    }
}

int nrCif(int x)
{
    int nr=0;
    do
    {
        nr++;
        x/=10;
    }while(x);
    return nr;
}

void afis()
{
    int nr=nrCif(rez[1][0]);
    for(int i=1; i<=c-nr; i++)
        printf("0");
    printf("%d", rez[1][0]);
}

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

    scanf("%s", nrA);
    l=strlen(nrA);
    if(nrA[l-1] == '\n')
        nrA[--l]=0;
    scanf("%s", b);
    lb=strlen(b);
    if(b[lb-1] == '\n')
        b[--lb]=0;
    scanf("%d", &c);
    modul();
    calcA();
    formMat();
    ridica(mat, rez);
    afis();
    return 0;
}