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
.
Constraints
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
Comments