#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("calcul.in");
ofstream fout("calcul.out");

const int NMax = 100005;
char s[NMax];
bool biti[4*NMax];
int a,c, mod;

void Read()
{
    fin>>s;

    int l = strlen(s);
    int st = max(0,l-9);
    /// ma intereseaza maxim ultimele 9 cifre
    for(int i=st; i<l; ++i)
        a = a*10 + s[i] - '0';

    memset(s,0,sizeof(s));

    fin >> s;
    l = strlen(s);

    for(int i=0; i<l; ++i)
    {
        int cif;
        if(isdigit(s[i]))
            cif = s[i] - '0';

        else
            cif = s[i] - 'A' + 10;

        for(int j=0; j<4; ++j)
        {
            ///calculez bitii lui B
            biti[4*(l-i-1)+j+1] = (cif & (1<<j));
        }
    }

    fin >> c;
    mod = 1;
    for(int i=1; i<=c; ++i)
        mod *= 10;

    a=a%mod;

}

void Solve_and_Print()
{
    int l = 4*strlen(s);

    int rez = 0, a_b = a, sum = a;

    for(int i=1; i<=l; ++i)
    {
        if(biti[i]==true)
        {
            rez = (1LL * rez * a_b + sum)%mod;
        }

        sum = (1LL * sum * (1+a_b))%mod;
        a_b = (1LL * a_b * a_b)%mod;
    }

    int rezultat[NMax];
    /// urmeaza sa adaug 0-urile aferente
    while(rez > 0)
    {
        rezultat[++rezultat[0]] = rez%10;
        rez/=10;
    }

    rezultat[0] = c;

    for(int ind = rezultat[0]; ind>=1; --ind)
        fout << rezultat[ind];

    fout << "\n";
}

int main()
{
    Read();
    Solve_and_Print();
    return 0;
}