/*
TASK: string
LANG: C++
*/

#include <cstdio>
#include <cstring>

const int MAXL = 1 << 11;
const int MAXT = 1 << 6;//64
const int MOD = 1000000;

int N, T;
char s[MAXL];
int fl[MAXL];
char t[MAXT];
int pre[MAXL][MAXT];
int P;

void kmp_init () {
	fl[0] = fl[1] = 0;
	int crnt = 0;
	int i, j;
	for (i = 2; i <= N; ++i) {
		while (crnt && s[crnt] != s[i-1]) crnt = fl[crnt];
		if (s[crnt] == s[i-1]) ++crnt;
		fl[i] = crnt;
	}
//	for (i = 0; i <= N; ++i) printf ("%d ", fl[i]);	printf ("\n");
	for (i = 0; i <= N; ++i)
		for (j = 0; j < T; ++j) {
			crnt = i;
			while (crnt && s[crnt] != t[j]) crnt = fl[crnt];
			if (s[crnt] == t[j]) ++crnt;
			pre[i][j] = crnt;
		}
}
int dp[2][MAXL];
int main () {
	gets (s); N = strlen (s);
	gets (t); T = strlen (t);
	scanf ("%d", &P);

	kmp_init ();

	int c = 1, o = 0;
	int i, j, k;
	for (i = 0; i < N; ++i) dp[0][i] = 1; dp[0][N] = 0;
	for (i = P-1; i >= 0; --i) {
		memset (dp[c], 0, sizeof (dp) / 2);
	
		for (j = 0; j < N; ++j) {
			for (k = 0; k < T; ++k)
				dp[c][j] += dp[o][pre[j][k]];
			dp[c][j] %= MOD;
//			printf (" %d", dp[c][j]);
		}
//		puts ("");

		o = c;
		c = !c;
	}

	printf ("%d\n", dp[o][0]);

	return 0;
}
