#include <iostream>
#include <fstream>
#include <cstring>
#include <unordered_map>
using namespace std;

ifstream f("calcul.in");
ofstream g("calcul.out");

char nrA[100005];
char nrB[50005];

long long c, zecelaputere, aux, mat[4][4], matinit[4][4], a, lnrA, mati[4][4];

unordered_map<char,string>b16;

void preconfig()
{
    aux=c;
    zecelaputere=1;
    while (aux)
    {
        zecelaputere*=10;
        aux--;
    }

    aux=c;
    lnrA=strlen(nrA);
    int p=1;
    for (long long i=lnrA-1; aux && i>=0; --aux, --i)
    {
        a=a+p*(nrA[i]-'0');
        p*=10;
    }

    b16['0']="0000";
    b16['1']="0001";
    b16['2']="0010";
    b16['3']="0011";
    b16['4']="0100";
    b16['5']="0101";
    b16['6']="0110";
    b16['7']="0111";
    b16['8']="1000";
    b16['9']="1001";
    b16['A']="1010";
    b16['B']="1011";
    b16['C']="1100";
    b16['D']="1101";
    b16['E']="1110";
    b16['F']="1111";

    matinit[1][1]=1;
    matinit[2][1]=0;

    mat[1][1]=1;
    mat[1][2]=0;
    mat[2][1]=a;
    mat[2][2]=a;

    mati[1][1]=mati[2][2]=1;
}

void inmultire_mat(long long matdest[4][4], long long matsursa[4][4])
{
    long long auxi[4][4];
    for (long long i=1; i<=2; ++i)
        for (long long j=1; j<=2; ++j)
            auxi[i][j]=0;
    for (long long k=1; k<=2; ++k)
    {
        for (long long i=1; i<=2; ++i)
        {
            for (long long j=1; j<=2; ++j)
            {
                auxi[k][i]+=(matdest[k][j]*matsursa[j][i]);
                auxi[k][i]%=zecelaputere;
            }
        }
    }
    for (long long i=1; i<=2; ++i)
    {
        for (long long j=1; j<=2; ++j)
            matdest[i][j]=auxi[i][j];
    }
}

void ridicare_put()
{
    long long lnrB=strlen(nrB);
    for (long long i=lnrB-1; i>=0; --i)
    {
        for (long long j=3; j>=0; --j)
        {
            if(b16[nrB[i]][j]=='1')
                inmultire_mat(mati,mat);
            inmultire_mat(mat,mat);
        }
    }
}

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

int main()
{
    f >> nrA;
    f >> nrB;
    f >> c;
    preconfig();
    ridicare_put();
    inmultire_mat(mati,matinit);
    int nr_l=nrcifre(mati[2][1]);
    for (int i=1; i<=c-nr_l; ++i)
        g << '0';
    g << mati[2][1];
    return 0;
}