/*
TASK:string
LANG:C++
*/
#include <stdio.h>
#include <string.h>
#define mod 1000000
#define maxl 2048
#define FOR(i,n) for(int i=0;i<n;i++)

char s[maxl];
char t[maxl];
int dp[ maxl ][ maxl ];
int p;
int slen,tlen;

void init() {
     scanf("%s",&s);
     scanf("%s",&t);
     slen = strlen(s);
     tlen = strlen(t);
     scanf("%d",&p);
}

int solve(int ind,int matched) {
    if(dp[ ind ][ matched ] != -1) return dp[ ind ][ matched ];
    if(matched>=slen) return dp[ind][matched] = 0;
    if(ind == p) return dp[ind][matched] = 1;
    int res = 0;
    FOR(i, tlen) {
           if( s[ matched ] == t[ i ]) {
               res = (res + solve(ind+1, matched+1) ) % mod;
           }
           else {
                res = (res + solve(ind+1, 0) ) % mod;
           }
    }
    return dp[ind][matched] = res;
}

int main() {
    init();
    memset(dp,-1,sizeof dp);
    printf("%d\n",solve(0,0));
    return 0;
}
