当前没有测试数据。

Ex - 跑马灯

得分：600分

问题描述

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

公告板的显示循环周期为$L+W-1$个状态，当$S$的最后一个字符从左边消失时，$S$的第一个字符从右边出现。

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

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

(.代表没有显示字符的位置)

更准确地说，对于$0 \leq k \leq L+W-2$，当显示状态如下：

• 令$f(x)$表示$x$除以$L+W-1$的余数。当$f(i+k)<L$时，公告板的左边第$(i+1)$个位置显示$S$的$(f(i+k)+1)$个字符。否则，不显示任何字符。

现在，给出一个长度为$W$的字符串$P$，该字符串由大写和小写英文字母，以及.和_组成。
找出在公告板的$L+W-1$个状态中，与$P$除了_位置之外的字符相同的状态的数量。
更准确地说，找出满足以下条件的状态的数量：

• 对于每个$1 \leq i \leq 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$

输出

输出答案。

---

3 5
ABC
..___

3

有三个满足要求的状态，公告板显示....A，...AB，..ABC。

---

11 15
abracadabra
__.._________ab

2

---

20 30
abaababbbabaabababba
__a____b_____a________________

2

---

1 1
a
_

1