#include <fstream>
#include <cstring>
#define NM 50010

using namespace std;

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

long long MOD=1;
int C;
int i,j;
long long A;
int NB;
bool Bit[NM];
string SA,SB;
int PT;//which
//containment breach
long long In[2][2];//insanidade
long long B[2][2];//one late night
long long AUX[2][2];//eyes
long long R[2][2];//slender

void Inmult (long long A[2][2], long long B[2][2], long long C[2][2])
{
    int i,j,k;
    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
            for (k=0; k<2; k++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
}

int main ()
{
    getline(f,SA);
    getline(f,SB);
    f >> C;
    PT=C;
    for (i=1; i<=C; i++)
        MOD=10*MOD;

    for (i=0; i<SA.size(); i++)
        A=(1LL*(SA[i]-'0')+A*10)%MOD;

    for (i=SB.size()-1; i>=0; i--)
    {
        if (isdigit(SB[i]))
            C=SB[i]-'0';
        /*
        memset(AUX, 0, sizeof(AUX));
        */
        else
            C=10+SB[i]-'A';

        for (j=1; j<=4; j++)
        {
            Bit[++NB]=(C&1);
            C>>=1;
        }
    }

    In[0][1]=1;
    B[0][0]=B[1][0]=A;
    B[1][1]=1;
    R[0][0]=R[1][1]=1;

    for (i=1; i<=NB; i++)
    {
        if (Bit[i])
        {
            memset(AUX,0,sizeof(AUX));
            Inmult(R,B,AUX);
            memcpy(R,AUX,sizeof(R));
        }

        memset(AUX,0,sizeof(AUX));
        Inmult(B,B,AUX);
        memcpy(B,AUX,sizeof(B));
    }

    memset(AUX,0,sizeof(AUX));
    Inmult(In,R,AUX);

    if (AUX[0][0]==0)
    {
        for (i=1; i<=PT; i++)
            g << 0;
        g << '\n';

        f.close();
        g.close();

        return 0;
    }

    MOD/=10;
    while (AUX[0][0]<MOD)
    {
        g << 0;
        MOD/=10;
    }

    g << AUX[0][0] << '\n';

    f.close();
    g.close();

    return 0;
}