Description

There are two strings $A$ and $B$ consisting only of lowercase English letters.

We will select $k$ pairwise non-overlapping, non-empty substrings from string $A$, then concatenate these $k$ substrings in the order they appear in $A$ to obtain a new string. How many ways are there to make this new string equal to string $B$?

Note: Different selection positions are considered different ways.

Input Format

The first line contains three positive integers $n, m, k$, representing the length of string $A$, the length of string $B$, and the $k$ mentioned in the problem statement, respectively. Each pair of integers is separated by a single space.

The second line contains a string of length $n$, which is string $A$.

The third line contains a string of length $m$, which is string $B$.

Output Format

Output a single integer, the number of required ways.

Since the answer may be large, output the result modulo $1000000007$.

6 3 1 
aabaab 
aab

2

6 3 2 
aabaab 
aab

7

6 3 3 
aabaab 
aab

7

Hint

Sample Explanation

All valid ways are as follows (the underlined parts indicate the selected substrings):

Sample 1: $\texttt{\underline{aab}\,aab,aab\,\underline{aab}}$.

Sample 2: $\texttt{\underline{a}\,\underline{ab}\,aab,\underline{a}\,aba\,\underline{ab},a\,\underline{a}\,ba\,\underline{ab},aab\,\underline{a}\,\underline{ab},\underline{aa}\,\underline{b}\,aab,\underline{aa}\,baa\,\underline{b},aab\,\underline{aa}\,\underline{b}}$.

Sample 3: $\texttt{\underline{a}\,\underline{a}\,\underline{b}\,aab,\underline{a}\,\underline{a}\,baa\,\underline{b},\underline{a}\,ab\,\underline{a}\,a\,\underline{b},\underline{a}\,aba\,\underline{a}\,\underline{b},a\,\underline{a}\,b\,\underline{a}\,a\,\underline{b},a\,\underline{a}\,ba\,\underline{a}\,\underline{b},aab\,\underline{a}\,\underline{a}\,\underline{b}}$.

Constraints

For testdata 1: $1 \le n \le 500, 1 \le m \le 50, k = 1$;

For testdata 2 to 3: $1 \le n \le 500, 1 \le m \le 50, k = 2$;

For testdata 4 to 5: $1 \le n \le 500, 1 \le m \le 50, k = m$;

For testdata 1 to 7: $1 \le n \le 500, 1 \le m \le 50, 1 \le k \le m$;

For testdata 1 to 9: $1 \le n \le 1000, 1 \le m \le 100, 1 \le k \le m$;

For all 10 testdata sets: $1 \le n \le 1000, 1 \le m \le 200, 1 \le k \le m$.

Translated by ChatGPT 5