Byteasar 参加了一门速读课程，课程教了他许多提高感知能力的练习。他最喜欢的一个练习是在符号序列中寻找模式。为了完成这个练习，Byteasar 让计算机生成了一个非常长的 0 和 1 序列，生成规则如下：他选择四个整数 $n, a, b$ 和 $p$，使得 $n$ 和 $a$ 互质，计算机生成序列 $c_0, c_1, \dots, c_{n-1}$，其中 $c_i = 0$ 当且仅当 $(ai+b) \pmod n < p$。最后，Byteasar 给出了另一个较短的符号序列 $w_0, w_1, \dots, w_{m-1}$。他的任务是尽快找出较短序列在计算机生成的序列中出现的所有次数。他请求你编写一个程序，来验证他是否确实找到了所有的出现次数。

输入格式

标准输入的第一行包含五个整数 $n, a, b, p$ 和 $m$ ($2 \le n \le 1\,000\,000\,000, 1 \le p, a, b, m < n, 1 \le m \le 1\,000\,000$)，以空格分隔。数字 $a$ 和 $n$ 互质。第二行包含一个由 $m$ 个符号组成的字符串 $w_0, w_1, \dots, w_{m-1}$，每个符号均为 0 或 1。

以下互斥的类别构成了所有测试数据的子集： 在总分 8% 的测试中，$n \le 1000$； 在总分 8% 的其他测试中，$n \le 1\,000\,000$； * 在总分 66% 的另一些测试中，$m \le 1000$。

输出格式

标准输出的第一行且仅包含一行，应包含一个整数，等于序列 $w_0, w_1, \dots, w_{m-1}$ 在序列 $c_0, c_1, \dots, c_{n-1}$ 中出现的次数。

样例

输入 1

9 5 6 4 3
101

输出 1

3

说明

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

序列 101 在序列 101011010 中出现了三次。