题目背景

题目描述

enana 给了你一个长度为 $n$ 的序列 $\{a\}$，$q$ 次操作：

1. 1 l r k 记 $f(x)=x(x+2)$，对 $[l,r]$ 内的每个 $i$ 执行 $k$ 次 $a_i\leftarrow f(a_i)$；
2. 2 l r 查询区间 $[l,r]$ 内的所有非空子序列的元素之积的和。

答案对 $10^9+7$ 取模。

输入格式

本题输入量较大，可以使用在题目最后给出的快读板子。

第一行三个正整数 $n,q,\text{type}$，即序列长度和操作次数，以及是否简化输出。

第二行 $n$ 个正整数 $a_i$，表示 $\{a\}$ 中元素。

之后 $q$ 行，每行 $3\sim4$ 个正整数，表示一次操作，保证输入数据合法。

输出格式

如果 $\text{type}=0$，对于每次询问输出对应的答案；否则输出每次询问答案的异或和。

保证当 $q>10^5$ 时 $\text{type}=1$。

6 6 0
1 2 3 4 5 6
2 1 3
2 3 6
1 1 3 1
2 1 3
2 3 5
2 4 6

23
839
575
479
209

提示

下设 $p=10^9+7$。

对于所有数据，$1\leq n,q\leq10^6,\text{type}\in\{0,1\},1\leq l\leq r\leq n,1\leq a_i,k<p-1$。

本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到该子任务的分数。

特殊性质 A：对于操作 $1$，$l=r$。
特殊性质 B：对于操作 $2$，$l=r$。

快读板子：

#define IOSIZE (1 << 20)
char buf[IOSIZE], *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, IOSIZE, stdin), p1 == p2) ? EOF : *p1++)
inline int read() { int x = 0; char c = '%'; while (c < '0' || c > '9') c = gc(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc(); return x; }

在控制台调试时，输入完成后需要键入 Ctrl + Z。