单点时限: 2.0 sec
内存限制: 512 MB
… Why don’t you come to the planetarium?
The beautiful twinkling of eternity that will never fade, no matter what.
All the stars in the sky are waiting for you…
A planetarium, it was once where people went to soothe their hearts by gazing at a starry sky.
And Yumemi, a planetarium guide who has been waiting for a visitor for a long time, is looking up at the stars.
Stars in the sky can be defined by their brightness, denoted by $S=\{b_1,b_2,\cdots,b_n\}$.
Yumemi found that stars always appear in groups, and she thinks the beauty of the starry night depends on the darkest one, so she defined the beauty value as
$$
B(S)=\sum_{1 \leq l \leq r \leq |S|}f(l,r) \ \text{mod}\ 998244353
$$
where
$$
f(l,r)=\min\limits_{l\leq i \leq r}\{b_i\}
$$
But the night sky is not always the same. The movement of celestial bodies will make more and more stars in the night sky. The following events will happen in order every second:
At the beginning, there is no star in the sky, so $S=\{\}$ initially.
As time goes by, because she is not as good at calculation as before, the task will be given to you.
Note that the sequence is given in a modified way.
To avoid huge input, we use Linear Congruential Method to generate input data, and your solution should be on-line.
The first line contains six integers $n,p,x,y,z,b_1(1 \leq n \leq 10^7,2 \leq p \leq 10^9,0 \leq x,y,z ,b_1 < p)$, indicating the number of the stars and the parameters of the data generator.
You need to generate the sequence $\{b_1,b_2,\cdots,b_n\}$ by yourself using the following formula:
$$
b_{i+1}=(x\times A_i+y \times b_i + z)\ \text{mod}\ p
$$
where $A_i$ is the value of $B(S)$ when $|S|=i$ .
To avoid huge output, you only need to output $\bigoplus\limits_{1\leq i \leq n} A_i$, where “$\bigoplus$” denotes the bitwise XOR operation.
5 13 2 0 1 3
27
In the first second, $S=\{b_1\}=\{3\}$, so $A_1=f(1,1)\ \text{mod}\ 998244353=3$.
It can be inferred that $b_2=(2A_1+1)\ \text{mod}\ 13=7$.
In the second second, $S=\{b_1,b_2\}=\{3,7\}$, so $A_2=[f(1,1)+f(2,2)+f(1,2)]\ \text{mod}\ 998244353=13$.
It can be inferred that $b_3=(2A_2+1)\ \text{mod}\ 13=1$.
Keep calculating, and you will get $A_3=16,b_4=7,A_4=26,b_5=1,A_5=31$.
So you should output $A_1 \bigoplus A_2 \bigoplus A_3 \bigoplus A_4 \bigoplus A_5=27$.