Background

Special for beginners, ^_^

Description

现在有一个序列，满足如下的递推关系： x[i] = (ax[i−1] + c) mod m, • n, m, a 和 c 都是正整数 • x[0] 是非负整数 • 产生的序列不包含重复元素。 例如，如果n = 5, m = 8, a = 1, c = 3, 并且 x[0] = 3, 则序列是 6, 1, 4, 7, 2。 津津最近学了二分查找(mid = (low+high)/2), 如果mid找不到，二分查找算法不会再次搜索比较x[mid])，可以非常熟练的写出二分查找的代码。可是她学艺不精，忘了二分查找的前提是先排序。那么对于上述的没有排序的序列，如果调用正确的二分查找算法，问有多少个x[i]（i从1开始）可以被成功查找。

Format

Input

输入包含一行，包括5个正整数n, m, a, c和x[0] (1 ≤ n ≤ 1e6 , 1 ≤ m, a, c ≤ 2^31 − 1, 0 ≤ x[0] ≤ 2^31 − 1), 其中n是序列的长度并且保证序列不包含重复元素，其他的m, a, c和x0的含义如前所述。

Output

输出在忘了先排序再二分查找的情况下，序列中有多少个数可以被找到。

Samples

5 8 1 3 3

2

Limitation

1s, 1024KiB for each test case.