#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 1e5;

int a, c;
int n, m, k, cf;
int p, sol1, put;

char sol[2][1 + NMAX];
int ans[1 + NMAX];
int b[1 + NMAX];

int main() {
  cin >> (sol[0] + 1) >> (sol[1] + 1) >> c;
  put = 1;
  for(int i = 1; i <= c; i++)
    put *= 10;
  n = strlen(sol[0] + 1);
  m = strlen(sol[1] + 1);
  for(int i = max(n - c + 1, 1); i <= n; i++)
    a = a * 10 + (sol[0][i] - '0');
  for(int i = 1; i <= m; i++) {
    if('A' <= sol[1][i] && sol[1][i] <= 'F')
      cf = sol[1][i] - 'A' + 10;
    else
      cf = sol[1][i] - '0';
    for(int j = 3; j >= 0; j--)
      b[++k] = (cf >> j) % 2;
  }
  p = 1;
  for(int i = 1; i <= k; i++) {
    sol1 = 1LL * sol1 * (1 + p) % put;
    p = 1LL * p * p % put;
    if(b[i]) {
      p = 1LL * p * a % put;
      sol1 = (sol1 + p) % put;
    }
  }
  for(int i = c; i >= 1; i--) {
    ans[i] = sol1 % 10;
    sol1 /= 10;
  }
  for(int i = 1; i <= c; i++)
    cout << ans[i];
  return 0;
}