/*
TASK:string
LANG:C++
*/

#include <cstdio>
//#include <conio.h>
#include <algorithm>
using namespace std;

#define MN      3000
#define MAG     1000000

int g[MN][MN];
int f[MN];
char S[MN],T[MN];
int P;
int sn;
int tn;

int main()
{
    //freopen("a6.in","r",stdin);
    
    scanf("%s%s%d",S,T,&P);
    
    sn=strlen(S);
    tn=strlen(T);
    
    int i,q=0;
    f[0]=f[1]=0;
    for (i=2;i<=sn;++i) {
        while (q>0 && S[i-1]!=S[q]) q=f[q];
        if (S[i-1]==S[q]) ++q;
        f[i]=q;
        //printf("f[%d]=%d\n",i,q);
    }
    
    int p,j;
    char t;
    
    memset(g,0,sizeof(g));
    //for (int i=1;i<=sn;++i) printf("%d,",f[i]);printf("\n");
    
    for (j=0;j<tn;++j) {
        t=T[j];
        if (t==S[0]) g[1][1]++;
        if (t!=S[0]) g[1][0]++;
    }
    
    for (i=1;i<P;++i) {
        for (p=0; p<sn; ++p) {
            if (g[i][p]==0) continue;
            for (j=0; j<tn; ++j) {
                char t=T[j];
                
                q=p;
                while (q>0 && S[q]!=t) {q=f[q];}
                if (S[q]==t) ++q;
                g[i+1][q] = (g[i+1][q] + g[i][p]) % MAG;
            }
        }
    }
    
    int ans=0;
    for (p=0;p<sn;++p) {
        ans = (ans + g[P][p]) % MAG;
    }
    printf("%d\n",ans);
    
    
    //getch();
    return 0;
}
