/*
TASK: string
LANG: C
*/
#include <stdio.h>
#include <string.h>
#define MAXN 2010

 int g[MAXN][MAXN];
 int r[MAXN][MAXN];
 int c[MAXN][MAXN];
 int prev[MAXN];
 char a[MAXN];
 char b[MAXN];
 int n,m,t;
 int mod=1000000;
 int res;

 void mul (int a[MAXN][MAXN],int b[MAXN][MAXN])
  {
   int i,j,k;
   memset(c,0,sizeof(c));
   for (i=0;i<=n;i++)
    for (j=0;j<=n;j++)
     for (k=0;k<=n;k++)
      c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
  }

 int main ()
  {
   int i,q,j;
   b[0]=a[0]='!';
   scanf("%s",&a[1]);
   n=strlen(&a[1]);
   scanf("%s",&b[1]);
   m=strlen(&b[1]);
   q=0;
   for (i=2;i<=n;i++)
    {
     while (q!=0 && a[q+1]!=a[i])
      q=prev[q];
     if (a[q+1]==a[i])
      q++;
     prev[i]=q;
    }
   for (i=0;i<n;i++)
    for (j=1;j<=m;j++)
     {
      q=i;
      while (q!=0 && a[q+1]!=b[j])
       q=prev[q];
      if (a[q+1]==b[j]) q++;
      g[i][q]++;
     }
   g[n][n]+=m;
   for (i=0;i<=n;i++) r[i][i]=1;
   scanf("%d",&t);
   res=1;
   for (i=1;i<=t;i++)
    res=(res*m)%mod;
   for (;t;t>>=1)
    {
     if (t&1)
      {
       mul(r,g);
       memcpy(r,c,sizeof(c));
      }
     mul(g,g);
     memcpy(g,c,sizeof(c));
    }
   res=(res-r[0][n])%mod;
   if (res<0) res+=mod;
   printf("%d\n",res);
   return 0;
  }
