Byteasar 喜欢玩弄他在电脑上找到的随机（实际上是伪随机）位生成器。这个生成器的工作方式非常简单。当电脑启动时，会自动选择一个 $0$ 到 $m-1$ 之间的整数。这个整数被称为生成器的种子；我们用变量 $z$ 来表示它。然后，为了生成一个随机位，会调用以下函数。它计算出一个新的种子值，并用它来生成一个位：

$$z := \lfloor (z \cdot a + c) / k \rfloor \pmod m$$ 如果 $z < \lfloor m/2 \rfloor$ 则 返回 $0$ 否则 返回 $1$

数字 $a, c, k$ 是某些常数。Byteasar 调用了这个函数 $n$ 次，从而获得了一个位序列 $b_1, b_2, \dots, b_n$。现在他想知道初始种子的不同可能取值有多少个。

输入格式

第一行包含五个整数 $a, c, k, m$ 和 $n$ ($0 \le a, c < m, 1 \le k < m, 2 \le m \le 1\,000\,000, 1 \le n \le 100\,000$)。第二行包含一个长度为 $n$ 的字符串，由数字 $0$ 和 $1$ 组成；字符串的第 $i$ 个数字表示位 $b_i$。

输出格式

输出一个整数，表示在 $0$ 到 $m-1$ 范围内，可能是生成器初始种子的整数个数。

样例

样例输入 1

3 6 2 9 2
10

样例输出 1

4

说明

样例解释：生成器的初始种子可能等于 $1, 2, 7$ 或 $8$。