[AdditionalFile5637.zip](file://AdditionalFile5637.zip?type=additional_file)

#5637. 「PA 2015 Final」Neon

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Neon

Bajtazar 是比特托邦著名的恶作剧者。他以策划各种滑稽场景并将其拍摄成视频发布在网上为生。这一次，他把目标锁定在了一家声名显赫、名字极长的酒店屋顶上的大型霓虹灯。

霓虹灯展示的是由 $n$ 个字母组成的字符串 $w$，即该酒店的名称。Bajtazar 打算在深夜潜入酒店屋顶并熄灭霓虹灯中的某些字母，使得剩下的仍然亮着的字母从左到右阅读时，能构成一个非常有趣的、$m$ 个字母的单词 $s$。为了让整体效果更加震撼，最后一个亮着的字母与第一个亮着的字母的位置之差不能小于 $k$。这位恶作剧者想知道，他有多少种关掉字母的方式可以达成这一目标。

正式地，他感兴趣的是选择编号 $j_{1}, j_{2}, \ldots, j_{m}$ 的方案数，这些编号均在区间 $[1, n]$ 内，且满足 $j_{1}<j_{2}<\ldots<j_{m}$，$j_{m}-j_{1} \geq k$ 且 $w_{j_{1}} w_{j_{2}} \ldots w_{j_{m}}=s$，其中 $w_{i}$ 表示字符串 $w$ 的第 $i$ 个字母。编号 $j_{1}, j_{2}, \ldots, j_{m}$ 对应于保持亮着的字母的位置。

输入格式

输入的第一行包含三个整数 $n, m, k$ $(1 \leq k \leq n \leq 100000, 1 \leq m \leq 10)$。

第二行包含酒店屋顶上展示的 $n$ 个字母的单词 $w$。

第三行包含在关掉某些字母后需要展示的 $m$ 个字母的单词 $s$。

单词 $w$ 和 $s$ 均仅由小写英文字母 $(\texttt{a-z})$ 组成。

输出格式

在一行中输出 Bajtazar 达成目标的方案总数，结果对 $10^{9}+7$ 取模。

样例

输入

13 3 5
longlonghotel
lol

输出

5

Bajtazar 可以保留以下位置集合之一的字母亮着：$\{1, 2, 13\}$、$\{1, 6, 13\}$、$\{1, 10, 13\}$、$\{5, 6, 13\}$、$\{5, 10, 13\}$。