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

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

 int main ()
  {
   int i,q,j,k;
   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++)
     if (i!=n)
      {
       q=i;
       while (q!=0 && a[q+1]!=b[j])
        q=prev[q];
       if (a[q+1]==b[j]) q++;
       g[i][j]=q;
      }
       else
        g[i][j]=n;
   r[0]=1;
   scanf("%d",&t);
   res=1;
   for (i=1;i<=t;i++)
    {
     res=(res*m)%mod;
     memset(c,0,sizeof(c));
     for (k=0;k<=n;k++)
      for (j=1;j<=m;j++)
       {
        c[g[k][j]]=(c[g[k][j]]+r[k]);
        if (c[g[k][j]]>=mod)
         c[g[k][j]]-=mod;
       }
     memcpy(r,c,sizeof(c));
    }
   res=(res-r[n])%mod;
   if (res<0) res+=mod;
   printf("%d\n",res);
   return 0;
  }
