题目描述

In Minecraft, one way to become stronger is to have the armors and weapons enchanted. Enchanted books play an important role.

The most important attribute of an enchanted book is its level. The higher the level is, the better the book is. We could merge two books with the same level $l$ into one new book(the older two will disappear). The level of the new book is $l+1$ and the merger costs $2^{l+1}$.

Now, Steve has $n$ enchanted books numbered from $1$ to $n$. Initially, the $i$-th book's level is $a_i$. Steve asks you to help him with the following four operations.

1. Given two integers $l,r(1 \le l \le r \le n)$, calculate the maximum level Steve can reach by merging books numbered from $l$ to $r$.

2. Given three integers $l,r(1 \le l \le r \le n)$ and $k$, then follow the steps:
   Step $1$: Steve merges all the books numbered from $l$ to $r$ until there does not exist two books with the same level.
   Step $2$: Steve adds one new book with level $k$ to the books he gets in Step $1$.
   Step $3$: Steve needs to merge books he gets in Step $2$ and he wants to maximize the times he merges the books.
   Please calculate and output the total cost modulo $10^9+7$ in Step $3$.
   $\textbf{Note that, after calculating, the sequence is restored. That is, this operation does NOT actually change the sequence.}$

3. Given two integers $pos,k$, Steve changes the level of the book numbered $pos$ to $k$.

4. Given one integer $t$, Steve restores the sequence to the state after the $t$-th operation. If $t=0$, then Steve restores the sequence to the beginning state.

输入格式

The first and the only line contains 5 integers $n,m,A,p,q$.($1 \leq n \leq 10^6$, $1 \leq m \leq 10^6$, $1 \leq A \leq 19\,260\,817$, $1 \leq p \leq 4$, $1 \leq q \leq 30$)

Please pay attention! To avoid large input file, the true input is constructed through the following strategy:

$\textbf{Function rnd():}\ \ \ \\ A \leftarrow (7A+13) \bmod 19\,260\,817\ \ \ \\ \textbf{return } A$

Firstly, $n$ integers $a_1,a_2,\cdots,a_n$ are generated in turn, $a_i \leftarrow rnd() \bmod q + 1$.

Then, the parameters of all operations are generated.

For each operation, the number of operation(representing by $opt$) is firstly generated, $opt \leftarrow rnd() \bmod p + 1$.

According to the number of operation, the different method is applied to generate parameters for different operation.

• For operation 1: we need to get $l$ and $r$ by using:

  • $L \leftarrow rnd() \bmod n + 1$
  • $R \leftarrow rnd() \bmod n + 1$
  • $l \leftarrow \min(L,R)$
  • $r \leftarrow \max(L,R)$

• For operation 2: we need to get $l,r$ and $k$ by using:

  • $L \leftarrow rnd() \bmod n + 1$
  • $R \leftarrow rnd() \bmod n + 1$
  • $l \leftarrow \min(L,R)$
  • $r \leftarrow \max(L,R)$
  • $k \leftarrow rnd() \bmod q + 1$

• For operation 3: we need to get $pos$ and $k$ by using:

  • $pos \leftarrow rnd() \bmod n + 1$
  • $k \leftarrow rnd() \bmod q + 1$

• For operation 4: we need to get $t$ by using:

  • $t \leftarrow rnd() \bmod i$

Here, $i$ represents the $i$-th operation.

输出格式

For each operation 1 and 2, you need to output one single line with an integer, representing the answer to operation 1 and 2 modulo $10^9 + 7$.

6 3 2 1 3

1
3
2

10 15 5 4 7

0
9
9
0
64
0
0

提示

Function max means the maximum one between the parameters. Function min means the minimum one between the parameters.

In example 1, the initial books are $[1,2,3,1,2,3]$. The three operations' ranges are $[4,4]$, $[1,3]$ and $[4,5]$.