# 2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

G. Gentle Jena
PDF 题面可用

#### G. Gentle Jena

… 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:

1. There are exactly $i$ stars in the sky so $S=\{b_1,b_2,\cdots,b_i\}$. A star with brightness $b_{i+1}$ appears, and it will be appended to the end of the sequence $S$, so it will be $S=\{b_1,b_2,\cdots,b_{i+1}\}$.
2. Yumemi records the value (i.e., She calculates the value of $B(S)$).

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.

### 样例

Input
5 13 2 0 1 3

Output
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$.

NaN