/*
TASK:string
LANG:C++
*/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define MAXN 2048
#define MAXA 64
#define MOD 1000000

int dp[2][MAXA][MAXN];
int cnt[MAXN][MAXA];
int prev, cur;
char s[MAXN];
char a[MAXN];
char buf[MAXA];
int N, M, P;
int c[MAXN];

int slowSolve(int pos) {
    int res = 0;
    if (pos == N) {
        int i, j;
        for (i = 0; i < N-P+1; i++) {
            for (j = 0; j < P; j++) {
                if (c[i+j] != s[j]) {
                    break;
                }
            }
            if (j == P) {
                return 0;
            }
        }
        return 1;
    }
    c[pos] = 1;
    res += slowSolve(pos+1);
    c[pos] = 0;
    res += slowSolve(pos+1);
    return res;
}

int main() {
    
    gets(s);
    gets(a);
    gets(buf);

    sscanf(buf, "%d", &N);
    M = strlen(a);
    P = strlen(s);
    sort(a, a+M);
    
    for (int i = 0; i < P; i++) {
        for (int j = 0; j < M; j++) {
            if (s[i] == a[j]) {
                s[i] = j;
                break;
            }
        }
    }
    
    for (int i = 0; i < M; i++) {
        a[i] = i;
    }
    
    if (M == 2) {
        printf("%d\n", slowSolve(0));
        return 0;
    }
    
    bool flag = false;
    int kkk;
    for (kkk = 1; kkk < P; kkk++) {
        if (s[kkk] != s[kkk-1]) {
            break;
        }
    }
    if (kkk == P) {
        flag = true;
    }
    /*
    for (int i = 0; i < P; i++) {
        printf("%d ", s[i]);
    }
    printf("\n");
    for (int i = 0; i < M; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    */
    
    prev = 1;
    cur = 0;
    
    dp[0][M][0] = 1;
    /*
    for (int i = 1; i <= N; i++) { //global pos
        prev = 1 - prev;
        cur = 1 - cur;
        for (int j = 1; j <= M; j++) { //letter
            
            dp[cur][j][0] = (dp[prev][M][0] + dp[cur][j-1][0])%MOD;
            if (P >= 2 && s[1] == j-1) {
                dp[cur][j][0] = (dp[cur][j][0] - dp[prev][s[0]+1][0] + dp[prev][s[0]][0] + MOD)%MOD;
            }
            for (int k = 1; k <= P; k++) { //pos in string
                if (s[k-1] == a[j-1]) {
                    if (k == 1) {
                        dp[cur][j][k] = dp[prev][M][0];
                    }
                    else {
                        dp[cur][j][k] = dp[prev][s[k-2]+1][k-1];
                    }
                }
            }
            dp[cur][j][P+1] = (dp[cur][j-1][P+1] + dp[prev][M][P+1] + dp[prev][s[P-1]+1][P])%MOD;
        }
        printf("====== %d\n", i);
        for (int j = 1; j <= M; j++) {
            printf("letter %d: ", j);
            for (int k = 0; k <= P+1; k++) {
                printf("%d ", dp[cur][j][k]);
            }
            printf("\n");
        }
        printf("\n");
    }
    */
    
    for (int i = 1; i <= N; i++) { //global pos
        prev = 1 - prev;
        cur = 1 - cur;
        
        for (int j = 1; j <= M; j++) {
            dp[cur][j][0] = (dp[prev][M][0] + dp[cur][j-1][0])%MOD;
            for (int k = 1; k <= P; k++) {
                if (s[k-1] == a[j-1]) {
                    if (k == 1) {
                        dp[cur][j][k] = dp[prev][M][0];
                    }
                    else {
                        dp[cur][j][k] = dp[prev][s[k-2]+1][k-1];
                    }
                }
            }
            if (flag && a[j-1] == s[P-1]) {
                dp[cur][j][P+1] = (dp[cur][j][P] + dp[prev][M][P+1] + dp[cur][j-1][P+1])%MOD;
            }
            else {
                dp[cur][j][P+1] = (dp[cur][j][P] + 2*dp[prev][M][P+1] + dp[cur][j-1][P+1])%MOD;
            }
        }
    }
    
    //printf("%d - %d\n", dp[cur][M][0], dp[cur][M][P+1]);
    printf("%d\n", (dp[cur][M][0] - dp[cur][M][P+1] + MOD)%MOD);
    
    
    
    /*    
    int povt = (dp[cur][s[P-1]+1][P] + dp[cur][M][P+1]) % MOD;
    
    cnt[0][M] = 1;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cnt[i][j] = (cnt[i-1][M] + cnt[i][j-1]) % MOD;
        }
    }
    
    printf("%d - %d\n", cnt[N][M], povt);
    
    printf("%d\n", (cnt[N][M] + MOD - povt)%MOD );
    */
    return 0;
}
