## NOIP '15 P5 - Substring

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

Test Case

#### Input Specification

The first line will contain , , and , the length of string , the length of string , and the number of substrings to take from , respectively.

The second line will contain a string of length , string .

The third line will contain a string of length , string .

#### Output Specification

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

Since the answer can be very large, output the answer modulo .

#### Sample Input 1

6 3 1
aabaab
aab

#### Sample Output 1

2

#### Sample Input 2

6 3 2
aabaab
aab

#### Sample Output 2

7

#### Sample Input 3

6 3 3
aabaab
aab

#### Sample Output 3

7