/*
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;
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=1;i<l;i++) {
        j=0;
        while (s[j]==s[i+j]&&i+j<l)
              j++;
        if (i+j==l) {
           per=i;
           break;
           }
        }
    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;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;
    }
