P2679 [NOIP 2015 Senior] Substring

NOIP 2015 Day2T2.

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.

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 a single integer, the number of required ways. Since the answer may be large, output the result modulo $1000000007$.

**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