Description

在《Minecraft》中，变得更强的一种方式是让盔甲和武器附魔。附魔书在其中扮演了重要角色。

附魔书最重要的属性是其等级。等级越高，书越好。我们可以将两本相同等级 $l$ 的书合并成一本新书（原来的两本书将消失）。新书的等级为 $l+1$，合并的费用为 $2^{l+1}$。

现在，Steve 有 $n$ 本编号从 $1$ 到 $n$ 的附魔书。最初，第 $i$ 本书的等级为 $a_i$。Steve 请你帮助他完成以下四种操作。

1. 给定两个整数 $l,r(1 \le l \le r \le n)$，计算通过合并编号从 $l$ 到 $r$ 的书能达到的最大等级。

2. 给定三个整数 $l,r(1 \le l \le r \le n)$ 和 $k$，然后按照以下步骤操作： 步骤 $1$：Steve 合并编号从 $l$ 到 $r$ 的所有书，直到不存在两本等级相同的书。 步骤 $2$：Steve 将一个新书等级为 $k$ 的书加入步骤 $1$ 中得到的书中。 步骤 $3$：Steve 需要合并步骤 $2$ 中得到的书，并希望最大化合并次数。 请计算并输出步骤 $3$ 中的总费用对 $10^9+7$ 取模的结果。 \textbf{注意，计算后，序列会恢复。也就是说，此操作实际上不会改变序列。}

3. 给定两个整数 $pos,k$，Steve 将编号为 $pos$ 的书的等级改为 $k$。

4. 给定一个整数 $t$，Steve 将序列恢复到第 $t$ 次操作后的状态。如果 $t=0$，则 Steve 将序列恢复到初始状态。

Input Format

第一行也是唯一一行包含 5 个整数 $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$)

请注意！为了避免输入文件过大，真实输入是通过以下策略构造的：

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

首先，生成 $n$ 个整数 $a_1,a_2,\cdots,a_n$，依次生成，$a_i \leftarrow rnd() \bmod q + 1$。

然后，生成所有操作的参数。

对于每个操作，首先生成操作编号（用 $opt$ 表示），$opt \leftarrow rnd() \bmod p + 1$。

根据操作编号，不同的操作使用不同的方法生成参数。

• 对于操作 1：需要通过以下方式获取 $l$ 和 $r$：

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

• 对于操作 2：需要通过以下方式获取 $l,r$ 和 $k$：

  • $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$

• 对于操作 3：需要通过以下方式获取 $pos$ 和 $k$：

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

• 对于操作 4：需要通过以下方式获取 $t$：

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

这里，$i$ 表示第 $i$ 次操作。

Output Format

对于每个操作 1 和 2，你需要输出一行整数，表示操作 1 和 2 的答案对 $10^9 + 7$ 取模的结果。

6 3 2 1 3

1
3
2

10 15 5 4 7

0
9
9
0
64
0
0

Hint

函数 max 表示参数中的最大值。函数 min 表示参数中的最小值。

在例子 1 中，初始书为 $[1,2,3,1,2,3]$。三个操作的范围分别是 $[4,4]$，$[1,3]$ 和 $[4,5]$。（由 ChatGPT 4o 翻译）