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\)