시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

You are given an array $A$ consisting of $N$ integers.

You are also given two integers $K$ and $L$.

You must divide the whole array $A$ into exactly $K$ nonempty intervals so that the length of each interval is not greater than $L$.

The cost of an interval $[S, E]$ is the bitwise XOR sum of all elements of $A$ whose indices are in $[S, E]$.

The score of a division is simply the maximum of the costs of all $K$ intervals in the division. You are interested in the best division: the one which minimizes the score of the division. Since this would be too simple for you, the problem is reversed.

You know the minimum score: the answer for the original problem is not greater than $X$. Now you want to know the maximum value of $K$.

입력

The first line of input contains three integers $N$, $X$ and $L$ which are described above ($1 \le L \le N \le 10^5$, $0 \le X < 268\,435\,456$).

The next line contains three integers $A_{1}$, $P$ and $Q$ ($0 \le A_{1}, P, Q < 268\,435\,456$). All subsequent integers of the array $A$ are generated using these three integers in the following way: for every integer $1 < k \le N$, $A_{k} = (A_{k - 1} \cdot P + Q) \bmod 268\,435\,456$.

출력

Print a single line containing the answer. If the answer does not exist, just print $0$.

예제 입력 1

3 1 2
1 1 1

예제 출력 1

2

예제 입력 2

3 0 3
1 1 1

예제 출력 2

1