#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

char A[100005];
char B[50005];
int C;

int x, mod, ans;
vector<bool> pw;

class Matrix {
  public:
   Matrix(initializer_list<int> il) {
      auto it = il.begin();
      for (int i : {0, 1})
         for (int j : {0, 1})
            a[i][j] = *(it++);
   }
   int* operator[](int i) { return a[i]; }
   Matrix operator*(const Matrix& other) const {
      Matrix ans = {0, 0, 0, 0};
      for (int i : {0, 1})
         for (int j : {0, 1})
            for (int k : {0, 1})
               ans.a[i][j] = (ans.a[i][j] + int64_t(a[i][k]) * other.a[k][j]) % mod;
      return ans;
   }
  private:
   int a[2][2];
};

void GetBinary(char hx) {
   int digit = (hx >= 'A' ? hx - 'A' + 10 : hx - '0');
   for (int i = 0; i < 4; ++i)
      pw.push_back(digit & (1 << i));
}

void Read() {
   scanf("%s%s%d", A, B, &C);

   int len = strlen(A);
   x = 0;
   for (int i = max(0, len - C); i < len; ++i)
      x = x * 10 + A[i] - '0';

   for (int i = strlen(B) - 1; i >= 0; --i)
      GetBinary(B[i]);

   mod = 1;
   for (int i = 0; i < C; ++i)
      mod *= 10;
}

void Solve() {
   Matrix a = {0, 1, 0, 0};
   Matrix b = {x, 0, x, 1};
   for (bool bit : pw) {
      if (bit)
         a = a * b;
      b = b * b;
   }
   ans = a[0][0];
}

int main() {
   freopen("calcul.in", "r", stdin);
   freopen("calcul.out", "w", stdout);

   Read();
   Solve();
   printf("%0*d\n", C, ans);
   return 0;
}