You are given two strings, $A$ and $B$, of lengths $N$ and $M$, respectively, containing lowercase English letters. You are also given a parameter $K$. You take out $K$ non-overlapping non-empty sub-strings from $A$ and concatenate them in the order in which they appear in $A$ to get a new string. Your task is to calculate the number of ways to make the new string and string $B$ equal. Since the answer can be large, calculate it modulo $10^9 + 7$.

Note that the two ways are different if at least one of the sub-strings is different at any position or the indices with which the sub-strings are made are different.

Input Format

• The first line contains a single integer $N$, denoting the length of the string $A$.
• The second line contains a single integer $M$, denoting the length of the string $B$.
• The third line contains a single integer $K$, denoting the number of substrings you need to take from $A$.
• The fourth line contains the string $A$, containing lowercase English letters without spaces.
• The fifth line contains the string $B$, containing lowercase English letters without spaces.

Output Format

Print the number of ways to build the string $B$ using exactly $K$ non-overlapping non-empty substrings from $A$ modulo $10^9 + 7$.

Constraints

$1 \leq N \leq 1000 \\ 1 \leq M \leq 200 \\ 1 \leq K \leq M$