#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char A[100005],B[50005],Bit[200005];
int c,a,MOD,NrBit;
void citire()
{
    int i,cif;
    f.getline(A,100005);
    f.getline(B,50005);
    int lgA=strlen(A);
    f>>c;
    MOD = 1;
    for(i = 1; i <= c; i++)
        MOD *= 10;
    a = 0;
    for(i = max(lgA-c, 0); i<lgA; i++)
        a=a*10+A[i]-'0';
    NrBit = 0;
    for(i = 0; B[i]!=0; i++)
    {
        if(B[i] >= 'A')
            cif = B[i] - 'A' + 10;
        else
            cif = B[i] - '0';
        for(int j = 3; j >= 0; j--)
            Bit[++NrBit] = (cif >> j) & 1;
    }
}
int main()
{
    citire();
    int P=1,S=0;
    for(int i=1; i<=NrBit; i++)
    {
        S=1LL*S*(1+P)%MOD;
        P=1LL*P*P%MOD;
        if(Bit[i])
        {
            P=1LL*P*a%MOD;
            S=(S+P)%MOD;
        }
    }
    g<<setw(c)<<setfill('0')<<S<<'\n';
}