NOIP '15 P5 - Substring - DMOJ: Modern Online Judge

NOIP '15 P5 - Substring

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

You have two non-empty strings $A$ ~A~ and $B$ ~B~ made out of lowercase letters. You can build new strings as follows: take $k$ ~k~ non-overlapping non-empty substrings of $A$ ~A~ and arrange them in a new string in the order they were initially in $A$ ~A~. Find how many of the strings that can be built in such a way are equal to $B$ ~B~.

Constraints

Test Case	$n$ ~n~	$m$ ~m~	$k$ ~k~
$1$ ~1~	$n \le 500$ ~n \le 500~	$m \le 50$ ~m \le 50~	$k = 1$ ~k = 1~
$2$ ~2~			$k = 2$ ~k = 2~
$3$ ~3~			$k = 2$ ~k = 2~
$4$ ~4~			$k = m$ ~k = m~
$5$ ~5~			$k = m$ ~k = m~
$6$ ~6~			$k \le m$ ~k \le m~
$7$ ~7~
$8$ ~8~	$n \le 1\,000$ ~n \le 1\,000~	$m \le 100$ ~m \le 100~
$9$ ~9~		$m \le 100$ ~m \le 100~
$10$ ~10~		$m \le 200$ ~m \le 200~
$11$ ~11~
$12$ ~12~

Input Specification

The first line will contain $n$ ~n~, $m$ ~m~, and $k$ ~k~, the length of string $A$ ~A~, the length of string $B$ ~B~, and the number of substrings to take from $A$ ~A~, respectively.

The second line will contain a string of length $n$ ~n~, string $A$ ~A~.

The third line will contain a string of length $m$ ~m~, string $B$ ~B~.

Output Specification

Output the number of ways to select $k$ ~k~ non-overlapping non-empty substrings of $A$ ~A~ such that their concatenation in order equals $B$ ~B~.

Since the answer can be very large, output the answer modulo $10^9 + 7$ ~10^9 + 7~.

Sample Input 1

6 3 1
aabaab
aab

Sample Output 1

Sample Input 2

6 3 2
aabaab
aab

Sample Output 2

Sample Input 3

6 3 3
aabaab
aab

Sample Output 3

Comments

There are no comments at the moment.