/*
TASK:string
LANG:C
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char S[2001], T[53];
short P, N, M;
long f[2000][2000], mp[2001];

void calcMp(void)
{
  short i;
  mp[0]=1;
  for(i=1; i<=P; ++i)
    mp[i]=(mp[i-1]*M)%1000000;
}

long calcf(void)
{
  short i, j;
  long res=0;
  f[0][0]=1;
  for(i=1; i<P; ++i)
  {
    for(j=f[i][0]=0; j<N-1; ++j)
      f[i][0]+=f[i-1][j];
    f[i][0]*=(M-1);
    for(j=1; j<N; ++j)
      f[i][j]=f[i-1][j-1];
    res+=f[i][N-1]*mp[P-i-1];
  }
  return res;  
}

int main(void)
{
  short i, j;
  memset(f, 0, sizeof f);
  gets(S);
  gets(T);
  N=strlen(S);
  M=strlen(T);
  scanf("%hd", &P);
  calcMp();
  printf("%ld\n", mp[P]-calcf());
  /*for(i=0; i<P; ++i)
  {
    for(j=0; j<N; ++j)
      printf("%ld ", f[i][j]);
    printf("\n");
  }*/
  system("PAUSE");
  return 0;
}
