测试数据来自 system/3063

作业已超过截止时间，您无法递交本题目。

单词提取

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

---

【问题描述】

　　有两个文本串 \(S\) 和 \(T\)，它们均是仅包含英文字母的字符串。

　　现在要从文本串 \(S\) 中取出 \(K\) 个单词（非空子串），且单词之间不能有重叠部分，然后把这 \(K\) 个单词按照在文本串 \(S\) 中出现的顺序依次连接起来得到一个新的文本串，那么有多少种方法可以使得这个文本串与 \(T\) 相等？

　　注意：只要单词提取的位置不同，就会认为是不同的方案。

【输入格式】

　　第一行是一个正整数 \(K\)，表示要提取的单词数量。接下来的两行分别是文本串 \(S\) 和文本串 \(T\)。文本串中仅含英文字母，没有其他符号。

【输出格式】

　　输出一个整数，表示所求方案数。答案可能很大，输出对 1,000,000,007 取模的结果。

【输入输出样例1】

　Input

2 
AACCACA
ACAC

　Output

3

【样例1说明】

　　三种提取方法如下，红色下划线的部分表示提取的单词：

【输入输出样例2】

　Input

3 
hhbhhb 
hhb

　Output

7

【数据限制】

　　下面的 \(|S|\) 表示文本串 \(S\) 的长度，\(|T|\) 表示文本串 \(T\) 的长度。
　　对于 \(30\ %\) 的数据满足：\(|S|≤500\)，\(|T|≤50\)，\(1≤K≤2\);
　　对于 \(70\ %\) 的数据满足：\(|S|≤500\)，\(|T|≤50\)，\(1≤K≤|T|\);
　　对于 \(100\ %\) 的数据满足：\(|S|≤1000\)，\(|T|≤200\)，\(1≤K≤|T|\);

【来源】

　　Mr.he