破译玛雅文字已被证明是一项比早期研究预期更艰巨的任务。在近两百年后，人们对它的了解仍然非常有限。直到最近三十年，才取得了实质性的进展。

玛雅文字基于被称为“字形”（glyphs）的小型图画，这些图画代表声音。玛雅单词通常由放置在不同位置的字形组合而成。

在破译玛雅文字时，遇到的几个问题之一是阅读顺序。当玛雅书写者放置多个字形以组成一个单词时，他们有时决定位置更多是基于个人的审美观点，而非任何特定的规则。这导致即使许多字形的读音已知，考古学家有时仍不确定如何读出一个书写的单词。

考古学家正在寻找一个特殊的单词 $W$。他们知道组成该单词的字形，但不知道排列这些字形的所有可能方式。由于他们知道你将参加 IOI'06，他们请求你的帮助。他们将提供 $W$ 中的 $g$ 个字形，以及他们在研究的雕刻中所有字形的序列 $S$（按它们出现的顺序）。请通过计算 $W$ 在 $S$ 中可能出现的次数来帮助他们。

任务

编写一个程序，给定 $W$ 的字形和雕刻中的字形序列 $S$，计算 $W$ 在 $S$ 中可能出现的次数；即计算 $S$ 中每一个长度为 $g$ 的连续子序列，且该子序列是 $W$ 中字形的一个排列。

数据范围

$1 \le g \le 3\,000$，$W$ 中的字形数量 $g \le |S| \le 3\,000\,000$，$|S|$ 为序列 $S$ 中的字形数量

输入格式

• 第 1 行：包含两个由空格分隔的整数，分别表示 $g$ 和 $|S|$。
• 第 2 行：包含 $g$ 个连续字符，表示 $W$ 中的字形。有效字符为 'a'-'z' 和 'A'-'Z'；大小写字母被视为不同。
• 第 3 行：包含 $|S|$ 个连续字符，表示雕刻中的字形。有效字符为 'a'-'z' 和 'A'-'Z'；大小写字母被视为不同。

输出格式

• 第 1 行：必须包含 $W$ 在 $S$ 中可能出现的次数。

子任务

对于总分 50 分的一组测试用例，每个测试运行都满足 $g \le 10$ 的要求。

说明

对于 Pascal 程序员的重要提示：在 FreePascal 中，默认情况下 string 类型变量的大小限制为 255 个字符。如果你想使用更长的字符串，应该在代码的 program ...; 行下方添加指令 {$H+}。

样例

输入格式 1

4 11
cAda
AbrAcadAbRa

输出格式 1

2