[ABC307Ex] Marquee

SK 酱定义字符串 $S$ 的一个 **$W$ 循环** 是一个如下所示的过程： （其中 $W=5,S=\texttt{ABC}$，`.` 表示此处无字符） - $\texttt{ABC..}$ - $\texttt{BC...}$ - $\texttt{C....}$ - $\texttt{....A}$ - $\texttt{...AB}$ - $\texttt{..ABC}$ - $\texttt{.ABC.}$ 不难发现，对于长度为 $L$ 的字符串 $S$ 的 $W$ 循环，一共有 $(L+W-1)$ 个状态。 SK 酱给你了长度为 $L$ 的字符串 $S$ 和长度为 $W$ 的字符串 $P$，其中 $S$ 仅由**大小写**英文字母构成，而 $P$ 仅由**大小写**英文字母，`.`（点）和 `_`（下划线）构成。 你需要帮她统计字符串 $S$ 的 $W$ 循环中的全部 $(L+W-1)$ 个状态中，能够与 $L$ 匹配（**`_` 的位置不要求，或者说 `_` 是通配符**）的状态的数量。 形式化地说，找到满足以下条件的状态数量： - 对于 $i=1,\cdots,W$，记当前状态为 $T$，则以下**至少一个**条件满足： - $P_i=$ `_`（下划线）； - $P_i=T_i$。 $T$ 中，**约定空的位置用 `.`（点）填充。** 对于 $100\%$ 的数据，保证： - $1\le L\le W\le 3\times 10^5$； - $S$ 仅由**大小写**英文字母构成； - $P$ 仅由**大小写**英文字母，`.`（点）和 `_`（下划线）构成。 $\text{Translated by @Starrykiller}$。

[problemUrl]: https://atcoder.jp/contests/abc307/tasks/abc307_h 英大文字および英小文字からなる長さ $ L $ の文字列 $ S $ が幅 $ W $ の電光掲示板に表示されており、$ S $ が右から左へ $ 1 $ 文字分の幅ずつスクロールするように切り替わっています。 表示は、$ S $ の最後の文字が左端から消えると同時に $ S $ の最初の文字が右端から現れる、$ L+W-1 $ 周期での繰り返しとなっています。 例えば $ W=5 $、$ S= $ `ABC` のとき、電光掲示板の表示は - `ABC..` - `BC...` - `C....` - `....A` - `...AB` - `..ABC` - `.ABC.` の $ 7 $ つの状態を繰り返します。（`.` は文字が表示されていないことを表します） より厳密には、各 $ k=0,\ldots,L+W-2 $ に対して、表示が次のようになっている相異なる状態が定まります。 - $ x $ を $ L+W-1 $ で割ったあまりを $ f(x) $ と表す。電光掲示板の左から $ (i+1) $ 番目の位置には、$ f(i+k)\ <\ L $ のとき $ S $ の $ f(i+k)+1 $ 番目の文字が表示され、そうでないとき何も表示されていない。 英大文字, 英小文字, `.`, `_` からなる長さ $ W $ の文字列 $ P $ が与えられます。 電光掲示板の $ L+W-1 $ 種類の状態のうち、`_` の箇所を除いて $ P $ と一致するものの個数を求めてください。 より厳密には、以下の条件を満たす状態の個数を求めてください。 - 全ての $ i=1,\ldots,W $ に対して次のいずれかが成立する - $ P $ の $ i $ 文字目は `_` である - 電光掲示板の左から $ i $ 番目に表示されている文字が $ P $ の $ i $ 文字目と等しい - 電光掲示板の左から $ i $ 番目には何も表示されておらず、かつ、$ P $ の $ i $ 文字目は `.` である

入力は以下の形式で標準入力から与えられる。 > $ L $ $ W $ $ S $ $ P $

答えを出力せよ。

3 5
ABC
..___

3

11 15
abracadabra
__.._________ab

2

20 30
abaababbbabaabababba
__a____b_____a________________

2

1 1
a
_

1

### 制約 - $ 1\ \leq\ L\ \leq\ W\ \leq\ 3\times\ 10^5 $ - $ L,W $ は整数である - $ S $ は英大文字および英小文字のみからなる長さ $ L $ の文字列である - $ P $ は英大文字, 英小文字, `.`, `_` のみからなる長さ $ W $ の文字列である ### Sample Explanation 1 電光掲示板の表示が `....A`, `...AB`, `..ABC` であるときの $ 3 $ 状態が該当します。