정렬되지 않은 채로

Ann Logan은 정수의 유한 수열에 관심이 많다. 그녀가 특히 흥미를 느끼는 것은 다음과 같은 형태의 수열 $x_1, x_2, \ldots, x_n$이다.

• $x_i = (a x_{i-1} + c) \bmod 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) \bmod 8 = 6$, $x_2 = (1 \cdot 6 + 3) \bmod 8 = 1$ 등). 처음 값 $x_0$은 수열의 일부로 보지 않는다.

Ann은 임의의 정수 값이 이런 형태의 유한 수열에 나타나는지 빠르게 판별하고 싶어 한다. $n, m, a, c, x_0$이 주어졌을 때 그녀가 세운 계획은 다음과 같다.

1. 수열 $x_1, \ldots, x_n$을 생성해 배열에 저장한다.
2. 배열을 정렬한다.
3. 관심 있는 각 정수에 대해 배열에서 이진 탐색을 수행한다.

Ann의 탐색 알고리즘은 가장 효율적이지는 않지만 이진 탐색에 익숙한 사람이라면 누구나 이해할 수 있을 만큼 단순하다. 각 단계에서 중간 위치 $mid = (low+high)/2$를 계산한 뒤, 그 위치의 값이 탐색 값 $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, \ldots, x_n$의 길이이고, $m, a, c, x_0$은 수열을 생성하는 데 쓰는 상수이다. 생성된 수열의 모든 값은 서로 다름이 보장된다.

Ann이 수열을 정렬하는 것을 잊었다고 가정했을 때, Ann의 이진 탐색으로 찾을 수 있는 수열 값의 개수를 출력한다.