#include <fstream>
#include <string>
#include <cstring>

using namespace std;

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

const int max_size = 3;

long long ans[3][3], inm[3][3], aux[3][3], rez[3][3], MOD;

long long bt[200001];

void prod (long long m1[3][3], long long m2[3][3], long long pr[3][3], int n, int m, int p)
{
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            aux[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= p; k++)
            {
                aux[i][j] = (aux[i][j] + m1[i][k] * m2[k][j]) % MOD;
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            pr[i][j] = aux[i][j];
        }
    }
}

void lgput (long long m[3][3], int n, int e)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            rez[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        rez[i][i] = 1; /// il fac I2
    }
    while (e != 0)
    {
        if (e % 2 == 1)
        {
            prod(rez, m, rez, n, n, n);
        }
        prod(m, m, m, n, n, n);
        e /= 2;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            m[i][j] = rez[i][j];
        }
    }
}

/// ma fut pe ele de matrice
/// tot iau 10 la sever anyway

int main ()
{
  string a, b;
  in >> a >> b;
  int c;
  in >> c;
  long long pl = 0;
  MOD = 1;
  for (int i = 1; i <= c; i++)
  {
    MOD *= 10;
  }
  for(int i = max(0, (int)a.size() - (int)MOD); i < a.size(); i++)
  {
		pl = pl * 10 + (a[i] - '0') * 1LL;
  }
  int biti = 0;
  for (int i = 0; i < b.size(); i++)
  {
    int nr = 0;
    if (isdigit(b[i]))
    {
      nr = b[i] - '0';
    }
    else
    {
      nr = b[i] - 'A' + 10;
    }
    for (int j = 4; j > 0; j--)
    {
      bt[++biti] = ((nr >> (j - 1)) & 1);
    }
  }
  long long ans = 0, sumcurr = pl, acurr = pl, suma = 1;
  for (int i = 1; i <= biti; i++)
  {
    ans = (ans * (suma + 1)) % MOD;
    suma = (suma * suma) % MOD;
    if (bt[i])
    {
      suma = (suma * pl) % MOD;
      ans = (ans + suma) % MOD;
    }
    //out << ans << " ";
  }
  MOD /= 10;
  while (ans < MOD && MOD > 0)
  {
    MOD /= 10;
    out << 0;
  }
  if (ans > 0)
  {
    out << ans;
  }
  in.close();
  out.close();
  return 0;
}