题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Kurs szybkiego czytania

Bajtazar 报名了一门快速阅读课程，学会了许多提升观察力的练习。他最爱的练习是在符号序列中寻找特定模式。他用计算机生成一个超长的 0 和 1 序列，方法是选择 $n, a, b, p$（$n$ 与 $a$ 互质），生成序列 $c_0, c_1, \ldots, c_{n-1}$，其中 $c_i = 0$ 当且仅当 $(a \cdot i + b) \bmod n < p$。接着，他设计一个较短的 $m$ 个符号序列 $w_0, w_1, \ldots, w_{m-1}$，目标是尽快找出这个短序列在长序列中的所有出现位置。Bajtazar 请你编写程序，验证他是否找全了这些位置。

输入格式

第一行包含五个整数 $n, a, b, p, m$ $(2 \leq n \leq 10^9, 1 \leq p, a, b, m < n, 1 \leq m \leq 1000000)$，分别表示长序列长度、生成参数、模式序列长度。$a$ 与 $n$ 互质。

第二行包含一个长度为 $m$ 的 $\texttt{0}$ 和 $\texttt{1}$ 序列 $w_0, w_1, \ldots, w_{m-1}$。

输出格式

输出一行，一个整数，表示序列 $w_0, w_1, \ldots, w_{m-1}$ 在 $c_0, c_1, \ldots, c_{n-1}$ 中的出现次数。

样例

输入

9 5 6 4 3
101

输出

3

对于 $n=9, a=5, b=6, p=4$，计算机生成序列如下：

序列 $\texttt{101}$ 在 $\texttt{101011010}$ 中出现 3 次。

附加样例

1. 在序列 $\texttt{10010000100100100100}$ 中寻找 $\texttt{0010}$ 的出现次数；
2. 在序列 $\texttt{0000000100000001000000000000001}$ 中寻找 $\texttt{00000}$ 的出现次数；
3. $n=1000000000, m=1000000$，在序列 $\texttt{00}\ldots\texttt{0011}\ldots\texttt{110}$（499999999 个 $\texttt{0}$，500000000 个 $\texttt{1}$，1 个 $\texttt{0}$）中寻找 $\texttt{011}\ldots\texttt{11}$（1 个 $\texttt{0}$ 后接全 $\texttt{1}$）的出现次数。

数据范围与提示

存在以下独立的测试点：

• $8\%$ 的数据，$n \leq 1000$；
• $8\%$ 的数据，$n \leq 1000000$；
• $66\%$ 的数据，$m \leq 1000$。