#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char s[100006];
bool Bit[200006];
int c, a, MOD = 1 ,nrb=0,S=0;
void citire()
{
    int n, cf, i;
    f >> s;
    n = strlen(s);
    c=9;
    a=0;
    for(int i=max(n-c,0);i<n;i++)
     a=a*10+s[i]-'0';
    /*
    c = 0;
    while(n >= 0 && c <= 9)
    {
        a += (s[n--] - '0') * p;
        p *= 10;
        c++;
    }
     */
    f >> s >> c;
    for(i = 1; i <= c; i++)MOD *= 10;
    a = a % MOD;
    for(int i = 0; s[i] != 0; i++)
    {
        if(s[i] < 'A')cf = s[i] - '0';
          else
            cf = s[i] - 'A' + 10;
        for(int j = 3; j >= 0; j--)
            Bit[++nrb] = (cf >> j) & 1;
    }
}

void calcul()
{
    int P = 1;
    for(int i = 1; i <= nrb; i++)
    {
        S = 1LL * S * (1 + P) % MOD;
        P = 1LL * P * P % MOD;
        if(Bit[i])
        {
            P = 1LL * P * a % MOD;
            S = (S + P) % MOD;
        }
    }
}
/*
void afisare(){
 for(int i=c-1;i>=0;i--){
  s[i]=S%10+'0';
  S/=10;
 }
 s[c]=0;
 g<<s;
}
*/
int main()
{
    citire();
    calcul();
    //afisare();
    g<<setw(c)<<setfill('0')<<S;
}