题目背景

NOIP2015 Day2T2

题目描述

给定两个仅包含小写英文字母的字符串 $A$ 和 $B$。

需要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后按照这些子串在 $A$ 中出现的顺序依次拼接成一个新字符串。问有多少种取法使得拼接后的新串恰好等于字符串 $B$？

注意：子串的取出位置不同也视为不同的方案。

输入格式

第一行是三个正整数 $n, m, k$，分别表示字符串 $A$ 的长度、字符串 $B$ 的长度，以及需要取出的子串个数，相邻整数间用一个空格隔开。

第二行包含一个长度为 $n$ 的字符串，表示字符串 $A$。

第三行包含一个长度为 $m$ 的字符串，表示字符串 $B$。

输出格式

一个整数，表示合法的取法总数。由于答案可能很大，输出对 $1000000007(10^9 + 7)$ 取模后的结果。

样例

6 3 1 
aabaab 
aab

2

6 3 2 
aabaab 
aab

7

6 3 3 
aabaab 
aab

7

提示

样例解释

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

样例 $1$：$\texttt{\underline{aab}\,aab,\ aab\,\underline{aab}}$。

样例 $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}}$。

样例 $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}}$。

数据范围

对于第 $1$ 组数据：$1 \leq n \leq 500,\ 1 \leq m \leq 50,\ k=1$。

对于第 $2$ 至第 $3$ 组数据：$1 \leq n \leq 500,\ 1 \leq m \leq 50,\ k=2$。

对于第 $4$ 至第 $5$ 组数据：$1 \leq n \leq 500,\ 1 \leq m \leq 50,\ k=m$。

对于第 $1$ 至第 $7$ 组数据：$1 \leq n \leq 500,\ 1 \leq m \leq 50,\ 1 \leq k \leq m$。

对于第 $1$ 至第 $9$ 组数据：$1 \leq n \leq 1000,\ 1 \leq m \leq 100,\ 1 \leq k \leq m$。

对于所有 $10$ 组数据：$1 \leq n \leq 1000,\ 1 \leq m \leq 200,\ 1 \leq k \leq m$。