时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有两个仅包含小写英文字母的字符串 \(A\) 和 \(B\)。现在要从字符串 \(A\) 中取出 \(k\) 个互不重叠的非空子串，然后把这 \(k\) 个子串按照其在字符串 \(A\) 中出现的顺序依次连接起来得到一 个新的字符串，请问有多少种方案可以使得这个新串与字符串 \(B\) 相等？注意:子串取出的位置不同也认为是不同的方案。

【输入格式】

　　第一行是三个正整数 \(n,m,k\)，分别表示字符串 \(A\) 的长度，字符串 \(B\) 的长度,以及问题描述中所提到的 \(k\)，每两个整数之间用一个空格隔开。 第二行包含一个长度为 \(n\) 的字符串,表示字符串 \(A\)。 第三行包含一个长度为 \(m\) 的字符串，表示字符串 \(B\)。

【输出格式】

　　输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对 1,000,000,007 取模的结果。

【输入输出样例1】

　Input

6 3 1 
aabaab 
aab

　Output

2

【输入输出样例2】

　Input

6 3 2
aabaab 
aab

　Output

7

【输入输出样例3】

　Input

6 3 3 
aabaab 
aab

　Output

7

【输入输出样例说明】

　　所有合法方案如下：（粗体部分表示取出的子串）

　　样例1： aab aab / aab aab

　　样例2： a ab aab / a aba ab / a a ba ab / aab a ab / aa b aab / aa baa b / aab aa b

　　样例3： a a b aab / a a baa b / a ab a a b / a aba a b / a a b a a b / a a ba a b / aab a a b

【数据限制】

　　对于第 \(1\) 组数据: \(1≤n≤500,1≤m≤50,k=1\);
　　对于第 \(2\)、\(3\) 组数据: \(1≤n≤500,1≤m≤50,k=2\);
　　对于第 \(4\)、\(5\) 组数据: \(1≤n≤500,1≤m≤50,k=m\);
　　对于第 \(6\)、\(7\) 组数据: \(1≤n≤500,1≤m≤50,1≤k≤m\);
　　对于第 \(8\)、\(9\) 组数据: \(1≤n≤1000,1≤m≤100,1≤k≤m\);
　　对于所有 \(10\) 组数据: \(1≤n≤1000,1≤m≤200,1≤k≤m\)。

【来源】

　　Mr.he