Problem Background

NOIP2015 Day2T2

Problem Description

There are two strings \( A \) and \( B \) containing only lowercase English letters.

You need to extract \( k \) non-overlapping, non-empty substrings from string \( A \). These \( k \) substrings should be concatenated in the order they appear in string \( A \) to form a new string. How many different ways can you do this such that the new string is equal to string \( B \)?

Note: Different positions from which the substrings are extracted are considered different schemes.

Input Format

The first line contains three positive integers \( n \), \( m \), and \( k \), representing the length of string \( A \), the length of string \( B \), and the number \( k \) mentioned in the problem, separated by spaces.

The second line contains a string of length \( n \), representing string \( A \).

The third line contains a string of length \( m \), representing string \( B \).

Output Format

An integer representing the number of ways to achieve the desired result, modulo \( 1000000007 \).

Sample Input and Output

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

Notes

Sample Explanation

All valid schemes are as follows (underlined parts represent the extracted 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}}\).

Data Range

For the first set of data: \(1 \leq n \leq 500, 1 \leq m \leq 50, k = 1\);
For the second to third sets of data: \(1 \leq n \leq 500, 1 \leq m \leq 50, k = 2\);
For the fourth to fifth sets of data: \(1 \leq n \leq 500, 1 \leq m \leq 50, k = m\);
For the first to seventh sets of data: \(1 \leq n \leq 500, 1 \leq m \leq 50, 1 \leq k \leq m\);
For the first to ninth sets of data: \(1 \leq n \leq 1000, 1 \leq m \leq 100, 1 \leq k \leq m\);
For all ten sets of data: \(1 \leq n \leq 1000, 1 \leq m \leq 200, 1 \leq k \leq m\).

见题面 Input 部分

见题面 Output 部分