#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];

int 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);
    for (int i=lnrA-1; aux && i>=0; --aux, --i)
    {
        a=a*10+(nrA[i]-'0');
    }

    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(int matdest[4][4], int matsursa[4][4])
{
    int aux[4][4];
    for (int i=1; i<=2; ++i)
        for (int j=1; j<=2; ++j)
            aux[i][j]=0;
    for (int k=1; k<=2; ++k)
    {
        for (int i=1; i<=2; ++i)
        {
            for (int j=1; j<=2; ++j)
            {
                aux[k][i]+=(matdest[k][j]*matsursa[j][i]);
                //aux[k][i]%=c;
            }
        }
    }
    for (int i=1; i<=2; ++i)
    {
        for (int j=1; j<=2; ++j)
            matdest[i][j]=aux[i][j];
    }
}

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

int main()
{
    f >> nrA;
    f >> nrB;
    f >> c;
    preconfig();
    ridicare_put();
    inmultire_mat(mati,matinit);
    cout << matinit[1][2];
    return 0;
}