Ann Logan 对有限整数序列非常着迷。她特别关注形式为 $x_1, x_2, \dots, x_n$ 的序列，其中：

• $x_i = (ax_{i-1} + c) \pmod m$
• $n, m, a, c$ 为正整数常量
• $x_0$ 为非负整数常量
• 所有 $n$ 个值均唯一

例如，若 $n = 5, m = 8, a = 1, c = 3, x_0 = 3$，则序列为 $6, 1, 4, 7, 2$（$x_1 = (1 \cdot 3 + 3) \pmod 8 = 6, x_2 = (1 \cdot 6 + 3) \pmod 8 = 1$，依此类推）。注意，她不将初始值 $x_0$ 视为序列的一部分。

Ann 希望能够快速确定任意整数值是否出现在这种形式的有限序列中。给定 $n, m, a, c$ 和 $x_0$ 的值，她计划执行以下步骤：

1. 生成序列 $x_1, \dots, x_n$ 并将其存储在数组中。
2. 对数组进行排序。
3. 对她感兴趣的每个整数执行二分查找。

Ann 的搜索算法虽然不是最高效的，但对于任何熟悉二分查找的人来说都非常直观且易于理解：在计算每一步的中间位置 mid 时（使用 mid = (low+high)/2），她首先检查位置 mid 处的值是否等于搜索值 $x$。如果不是，她会根据 $x$ 是严格小于还是严格大于位置 mid 处的值来缩小搜索范围。

不幸的是，Ann 很健忘，她弄丢了她的步骤清单。她只记得第一步和最后一步，但是……她在执行二分查找之前忘记对数组进行排序了！不用说，这意味着（未排序）数组中的许多值将无法通过二分查找找到，尽管令人惊讶的是，有些值仍然可以找到。在上面的例子中，数字 $4$ 和 $7$ 都可以通过 Ann 的二分查找找到。对于各种序列，有多少个值可以被找到？别搞砸了！

输入格式

输入包含一行，包含五个整数 $n, m, a, c$ 和 $x_0$（$1 \le n \le 10^6, 1 \le m, a, c \le 2^{31} - 1, 0 \le x_0 \le 2^{31} - 1$），其中 $n$ 是要生成的序列 $x_1, \dots, x_n$ 的长度，$m, a, c$ 和 $x_0$ 是用于生成序列的常量。保证生成的序列中所有值均唯一。

输出格式

输出在假设 Ann 忘记对序列进行排序的情况下，使用她的二分查找版本可以找到的序列值的数量。

样例

样例输入 1

5 8 1 3 3

样例输出 1

2

样例输入 2

6 10 1234567891 1 1234567890

样例输出 2

6