U605743 SegmentTree

HDU4578加强版（QwQ 不会写题面）。

Zxm 被下面这道题难住了： 有 $n$ 个整数 $a_1, a_2, ..., a_n$。现有四种操作： 操作1：将下标在 $[x,y]$ 的每个数都加上 $c$。 操作2：将下标在 $[x,y]$ 的每个数都乘上 $c$。 操作3：将下标在 $[x,y]$ 的每个数都变为 $c$。 操作4：将下标在 $[x,y]$ 的每个数 $p$ 次方之和。即计算 $a_x^p+a_{x+1}^p+...+a_y^p$。 Zxm 毫无头绪，于是想请你帮忙解决这个问题。

测试用例不超过 $10$ 组。 每组数据第一行包含两个整数 $n$ 和 $m$，表示有 $n$ 个整数和 $m$ 次操作（$1 \le n, m \le 100,000$）。 接下来一行描述原数列 $a_1, a_2, ..., a_n$。 随后 $m$ 行每行描述一个操作： 操作1至3的格式为：`1 x y c` 或 `2 x y c` 或 `3 x y c`； 操作4的格式为：`4 x y p` （其中 $1 \le x \le y \le n，1 \le c \le 10,000，1 \le p \le 10$）。 输入以 `0 0` 结束。

对于每个操作4，输出一行整数表示结果。由于答案可能很大，只需输出其对 $10^9+7$ 取模的结果。