题目描述

数据中心保存了一份长度为 $n$ 的原始日志 $S$，以及一份长度为 $m$ 的待复原记录 $T$。两个字符串都只包含小写英文字母。

现在需要从原始日志 $S$ 中选出恰好 $k$ 个非空连续片段，并按照它们在 $S$ 中从左到右出现的顺序依次拼接。

所选择的任意两个片段不能覆盖同一个位置。将这 $k$ 个片段拼接后，得到的字符串必须恰好等于 $T$。

两个方案只要选择的片段位置不同，就被视为不同方案，即使它们取出的字符内容完全相同。

请计算满足要求的片段选择方案数。

由于答案可能很大，请输出答案对 $1000000007$ 取模后的结果。

输入格式

第一行包含三个整数 $n,m,k$，分别表示原始日志 $S$ 的长度、待复原记录 $T$ 的长度，以及需要选择的片段数量。

第二行包含一个长度为 $n$ 的字符串 $S$。

第三行包含一个长度为 $m$ 的字符串 $T$。

字符串 $S$ 和 $T$ 均只包含小写英文字母。

输出格式

输出一个整数，表示满足要求的方案数对 $1000000007$ 取模后的结果。

样例

7 3 1
abacaba
aba

2

7 3 2
abacaba
aba

8

5 3 3
aaaaa
aaa

10

样例说明

第一个样例中，只选择一个连续片段。字符串 aba 在原始日志中出现了两次，对应位置分别为 $[1,3]$ 和 $[5,7]$，因此答案为 $2$。

第二个样例要求选择恰好两个互不重叠的非空片段。满足拼接结果为 aba 的方案共有 $8$ 种。

第三个样例中需要选择三个片段，而目标字符串长度也为 $3$，因此每个片段都只能包含一个字符。从原始日志的 $5$ 个位置中选择 $3$ 个位置，共有 $10$ 种方案。

数据范围

对于全部数据：

• $1\leq n\leq 1000$
• $1\leq m\leq 200$
• $1\leq k\leq m$