#include <cstdio>
#include <cassert>
#include <cstring>
#define Nmax 100005
#define InFile "calcul.in"
#define OutFile "calcul.out"

using namespace std;

int Mod, C, A, q;
char Sa[Nmax], Sb[Nmax/2], Sc[2];
int B2[2*Nmax];

void read();
void transform();
int suma ();

int main()
{
  int val, aux, i, nrc, nr0;
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  transform();
  val=suma();
  aux=val;
  do
  {
    nrc++;
    aux/=10;
  }
  while (aux);
  nr0=C-nrc;
  for (i=0; i<nr0; i++)
    printf ("0");
  printf ("%d\n", val);
  return 0;
}

void read()
{
  int i;
  scanf ("%s\n%s\n%s\n", Sa, Sb, Sc);
  C=Sc[0]-'0';
  Mod=1; for (i=0; i<C; i++) Mod*=10;
}

void transform()
{
  int i, j, val, lg=strlen (Sb);
  q=0;
  for (i=lg-1; i>=0; i--)
  {
    val=(Sb[i]>='A' && Sb[i]<='F')?(Sb[i]-'A'+10):(Sb[i]-'0');
    for (j=0; j<4; j++)
      B2[q++]=(val&(1<<j))?1:0;
  }
  while (!B2[q] && q>1) q--;
  lg=strlen (Sa);
  for (i=0; i<lg; i++)
    A=(A*10+(Sa[i]-'0'))%Mod;
}

int suma ()
{
  int i, sum=A, pt=A, as=A, apt=A;
  for (i=q-1; i>=0; i--)
  {
    as=((long long)sum*(long long)(pt+1))%Mod;
    apt=((long long)pt*(long long)pt)%Mod;
    if (B2[i])
    {
      as=((long long)as+(long long)(apt*A))%Mod;
      apt=((long long)apt*(long long)A)%Mod;
    }
    sum=as; pt=apt;
  }
  return sum;
}