/*
TASK: string
LANG: C
*/

#include <stdio.h>
#include <string.h>

#define MAX 2005
#define MOD 1000000

void input(void);
void solve(void);

int DP(int a, int b);

int get_it(char *a, int sa, char *b, int sb);

int n, m, len;
char S[MAX];
char A[MAX];

char pot[MAX];

int Z[MAX][55];

int F[MAX][MAX];

int main(void)
{
    input();
    solve();
    
    return 0;
}

void input(void)
{
     scanf(" %s", S); n = strlen(S);
     scanf(" %s", A); m = strlen(A);
     
     scanf("%d", &len);
}

void solve(void)
{
    int i, j;
    
    for(i = 0; i < MAX; i++)
      for(j = 0; j < MAX; j++) F[i][j] = -1;
      
    for(i = 0; i <= n; i++) pot[i] = S[i];
    
    for(i = 0; i < n; i++)
      for(j = 0; j < m; j++) {
        pot[i] = A[j]; pot[i + 1] = 0;
        Z[i][j] = get_it(pot, i + 1, S, n);
        pot[i] = S[i]; pot[i + 1] = S[i + 1];
      }
      
    printf("%d\n", DP(0, 0));
}

int get_it(char *a, int sa, char *b, int sb)
{
    int ans;
    int i, j;
    
    ans = 0;
    for(i = 0; i < sa; i++) {
      for(j = 0; j < sb && i + j < sa; j++) if(a[i + j] != b[j]) break;
      if(i + j == sa && j > ans) ans = j;
    }
    
    return ans;
}

int DP(int a, int b)
{
    int ans, z;
    int i, j;
    
    if(b > a || b == n) return 0;
    if(a == len)        return 1;
    if(F[a][b] != -1)   return F[a][b];

    ans = 0; 
    for(i = 0; i < m; i++) {
      /*
      pot[b] = A[i]; pot[b + 1] = 0; z = get_it(pot, b + 1, S, n);
      pot[b] = S[b]; pot[b + 1] = S[b + 1]; 
      */
      ans = (DP(a + 1, Z[b][i]) + ans) % MOD;
    }
    
    return F[a][b] = ans;
}
                
    
