/*
TASK:string
LANG:C
*/


//#define DEBUG

#include<stdio.h>
#define MOD 1000000

char s[2048];
char t[64];
char cp[8];

int p,l;
int num;
int per=-1;
int i,j,k;
int d[2][2048];

int main () {
    #ifdef DEBUG
    freopen("test.txt","rt",stdin);
    #endif
    gets(s);
    gets(t);
    gets(cp);
    sscanf(cp,"%d",&p);
    #ifdef DEBUG
    fclose(stdin);
    #endif
    l=strlen(s);
    num=strlen(t);
    for (i=0;i<l;i++)
        for (j=i+1;j<l;j++) {
            k=0;
            while (s[i+k]==s[j+k]&&j+k<l)
                  k++;
            if (j+k==l)
               per=i+1;
            }
    d[0][0]=1;
    for (i=1;i<l;i++)
        d[0][i]=(d[0][i-1]*num)%MOD;
    for (i=l;i<=p;i++) {
        d[1][i]=d[0][i-l];
        if (per!=-1) {
           for (j=i-l+per;j<i;j+=per)
               d[1][i]-=d[1][j];
           }
        d[1][i]%=MOD;
        d[0][i]=(d[0][i-1]*num-d[1][i]+MOD)%MOD;
        }
    printf("%d\n",d[0][p]);
    return 0;
    }
