#include <stdio.h>
#include <bitset>
#define M 1000000000
using namespace std;
int a,l,i,nr,c;
bitset <200050> p;
char A[100005];
long long power(){
  long long b[2][2],r[2][2],aux[2][2]; int i;
  b[0][0]=a;b[0][1]=a;
  b[1][0]=0;b[1][1]=1;
  r[0][0]=1;r[0][1]=0;r[1][0]=0;r[1][1]=1;
  for (i=l-1;i>=0;--i){
    if (p[i]){
      aux[0][0]=r[0][0]*b[0][0]+r[0][1]*b[1][0];
      aux[0][1]=r[0][0]*b[0][1]+r[0][1]*b[1][1];
      aux[1][0]=r[1][0]*b[0][0]+r[1][1]*b[1][0];
      aux[1][1]=r[1][0]*b[0][1]+r[1][1]*b[1][1];
      r[0][0]=aux[0][0]%M;r[0][1]=aux[0][1]%M;r[1][0]=aux[1][0]%M;r[1][1]=aux[1][1]%M;
    }
    aux[0][0]=b[0][0]*b[0][0]+b[0][1]*b[1][0];
    aux[0][1]=b[0][0]*b[0][1]+b[0][1]*b[1][1];
    aux[1][0]=b[1][0]*b[0][0]+b[1][1]*b[1][0];
    aux[1][1]=b[1][0]*b[0][1]+b[1][1]*b[1][1];
    b[0][0]=aux[0][0]%M;b[0][1]=aux[0][1]%M;b[1][0]=aux[1][0]%M;b[1][1]=aux[1][1]%M;
  }
return r[0][1];
}
int main(){
  freopen("calcul.in","r",stdin);
  freopen("calcul.out","w",stdout);
  scanf("%s\n",A);l=strlen(A);for (i=((l-9)>0)?(l-9):0;i<l;++i)a=a*10+A[i]-'0';
  scanf("%s\n",A);l=strlen(A);
  scanf("%d",&c);
  for (i=0;i<l;++i){
    nr=A[i];
    if (nr>='A'&&nr<='F')nr=nr-'A'+10;else nr=nr-'0';
    if (nr&8)p[i<<2]=1;
    if (nr&4)p[(i<<2)+1]=1;
    if (nr&2)p[(i<<2)+2]=1;
    if (nr&1)p[(i<<2)+3]=1;
  }
  l=l<<2;
  i=1;
  while (c)i*=10,c--;
  printf("%lld\n",power()%i);
return 0;
}