Bajtazar 是一位著名的 Byteotia 恶作剧者，他通过策划各种滑稽的场景并将其拍摄成视频发布在互联网上来谋生。这一次，他将目标对准了某家拥有超长名称的著名酒店屋顶上的巨大霓虹灯。

霓虹灯上的字母组成了一个长度为 $n$ 的字符串 $w$，即酒店的名称。Bajtazar 打算在夜间潜入酒店屋顶，熄灭其中的一些字母，使得剩下的发光字母从左到右读起来恰好构成一个非常滑稽的长度为 $m$ 的字符串 $s$。为了让效果更佳，最后发光字母的位置与第一个发光字母的位置之差不能小于 $k$。这位恶作剧者想知道，他有多少种熄灭字母的方法可以达到目的。

形式化地说，他感兴趣的是选择索引 $j_1, j_2, \dots, j_m$（满足 $1 \le j_1 < j_2 < \dots < j_m \le n$）的方法数，使得 $j_m - j_1 \ge k$ 且 $w_{j_1}w_{j_2}\dots w_{j_m} = s$，其中 $w_i$ 表示字符串 $w$ 的第 $i$ 个字母。索引 $j_1, j_2, \dots, j_m$ 对应于保持发光的字母位置。

输入格式

第一行包含三个整数 $n, m, k$（$1 \le k \le n \le 100\,000$，$1 \le m \le 10$）。 第二行包含一个长度为 $n$ 的字符串 $w$，表示屋顶上的霓虹灯。 第三行包含一个长度为 $m$ 的字符串 $s$，表示熄灭部分字母后要显示的字符串。 字符串 $w$ 和 $s$ 仅由小写英文字母（a-z）组成。

输出格式

在唯一的一行中输出 Bajtazar 可以达到目的的方法数，结果对 $10^9 + 7$ 取模。

样例

输入 1

13 3 5
longlonghotel
lol

输出 1

5

说明 1

Bajtazar 可以保留以下位置集合中的任意一个：$\{1, 2, 13\}, \{1, 6, 13\}, \{1, 10, 13\}, \{5, 6, 13\}, \{5, 10, 13\}$。