Substring

We are given two strings $A$ and $B$, both consisting only of lowercase English letters. We want to extract $k$ non-overlapping, non-empty substrings from $A$, and then concatenate these $k$ substrings in the order they appeared in $A$ to form a new string. How many ways can we do this such that the resulting string is equal to $B$? Note: different extraction positions are considered different ways.

Input

The first line contains three integers $n$, $m$, and $k$, representing the length of string $A$, the length of string $B$, and the value $k$ mentioned in the problem description, respectively. The integers are separated by a space.

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

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

Output

Output a single integer representing the number of ways. Since the answer can be very large, output the result modulo $1,000,000,007$.

Examples

Input 1

6 3 1
aabaab
aab

Output 1

2

Input 2

6 3 2
aabaab
aab

Output 2

7

Input 3

6 3 3
aabaab
aab

Output 3

7

Note

The valid ways are as follows (the underlined parts represent the extracted substrings):

Example 1: aab aab / aab aab

Example 2: a ab aab / a aba ab / a a ba ab / aab a ab / aa b aab / aa baa b / aab aa b

Example 3: a a b aab / a a baa b / a ab a a b / a aba a b / a a b a a b / a a ba a b / aab a a b

Constraints

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

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

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

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

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

For all 10 test cases: $1 \le n \le 1000$, $1 \le m \le 200$, $1 \le k \le m$.