题目描述

在宽度为 $W$ 的电子公告板上显示一个由大小写英文字母组成的长度为 $L$ 的字符串 $S$。字符串 $S$ 每次以一个字符的宽度从右向左滚动。

当字符串 $S$ 的最后一个字符从左边缘消失时，$S$ 会按循环周期 $L+W-1$ 进行重复显示，其中 $S$ 的第一个字符从右边缘出现。

例如，当 $W=5$，$S=$ ABC 时，公告板循环显示以下七个状态：

• ABC..
• BC...
• C....
• ....A
• ...AB
• ..ABC
• .ABC.

其中 . 表示不显示字符的位置。

更准确地说，在 $k=0,\\ldots,L+W-2$ 的每个不同状态下，显示如下所示。

• 设 $f(x)$ 是将 $x$ 除以 $L+W-1$ 的余数。当 $f(i+k)<L$ 时，第 $i+1$ 个位置从公告板的左侧显示 $S$ 的第 $f(i+k)+1$ 个字符；否则位置为空。

给定一个长度为 $W$ 的字符串 $P$，由大写字母、小写字母、. 和 _ 组成。请找出与 $P$ 相符的公告板的 $L+W-1$ 个状态中有多少个状态在 _ 的位置上除外与 $P$ 相同。

更准确地说，找出满足以下条件的状态数：

• 对于每个 $i=1,\\ldots,W$，以下情况之一成立：
  • $P$ 的第 $i$ 个字符是 _。
  • 公告板从左侧看的第 $i$ 个位置显示的字符与 $P$ 的第 $i$ 个字符相等。
  • 公告板从左侧看的第 $i$ 个位置没有显示字符，并且 $P$ 的第 $i$ 个字符是 .。

约束条件

• $1 \\leq L \\leq W \\leq 3\\times 10^5$
• $L$ 和 $W$ 是整数。
• $S$ 是由大写和小写英文字母组成的长度为 $L$ 的字符串。
• $P$ 是由大写和小写英文字母、. 和 _ 组成的长度为 $W$ 的字符串。

---

输入

输入数据从标准输入中获取，格式如下：

$L$ $W$ $S$ $P$

输出

打印答案。

---

示例输入 1

3 5
ABC
..___

示例输出 1

3

有三个符合条件的状态，公告板显示 ....A、...AB、..ABC。

---

示例输入 2

11 15
abracadabra
__.._________ab

示例输出 2

2

---

示例输入 3

20 30
abaababbbabaabababba
__a____b_____a________________

示例输出 3

2

---

示例输入 4

1 1
a
_

示例输出 4

1