P6215 函数求值

有两个长度均为 $n$ 的权值序列 $a,b$，常数 $p,k$，以及两个函数： $$g(x) = \sum_{i=1}^x p^i \times a_i$$ $$f(x) = \sum_{i=1}^x g(i) ^ k \times b_i$$ 有 $m$ 个操作，操作有以下三种： * $1\ x\ y$，表示将 $a_x$ 修改为 $y$。 * $2\ x\ y$，表示将 $b_x$ 修改为 $y$。 * $3\ x$，表示查询 $f(x)$ 对 $10 ^ 9 + 7$ 取模的值。

无

无

**【样例解释】** 这是样例一操作四后的结果： | $/$ | $1$ | $2$ | $3$ | $4$ | $5$ | | :-: | :-: | :-: | :-: | :-: | :-: | | $a_i$ | $0$ | $3$ | $8$ | $8$ | $5$ | | $b_i$ | $9$ | $2$ | $8$ | $8$ | $6$ | | $g(i)$ | $0$ | $3$ | $11$ | $19$ | $24$ | | $f(i)$ | $0$ | $6$ | $94$ | $246$ | $390$ | ---------------------- **【数据范围】** - 对于 $100\%%$ 的数据： $1 \le n,m \le 2 \times 10 ^ 5$。 $0 \le a_i,b_i,p \le 10 ^ 9 + 6$。 $1 \le x \le n$，$0 \le y \le 10 ^ 9 + 6$。 $1 \le k \le 3$。 - **详细的数据范围：** 测试点编号 | $n,m \le$ | $k$ | 特殊性质 :-: | :-: | :-: | :-: $1$ | $300$ | $\le 3$ | 无 $2$ | $300$ | $\le 3$ | 无 $3$ | $3 \times 10 ^ 3$ | $\le 3$ | 无 $4$ | $3 \times 10 ^ 3$ | $\le 3$ | 无 $5$ | $7 \times 10 ^ 4$ | $= 1$ | A $6$ | $7 \times 10 ^ 4$ | $= 1$ | A $7$ | $7 \times 10 ^ 4$ | $= 1$ | A $8$ | $7 \times 10 ^ 4$ | $= 2$ | A $9$ | $7 \times 10 ^ 4$ | $= 3$ | A $10$ | $7 \times 10 ^ 4$ | $= 1$ | B $11$ | $7 \times 10 ^ 4$ | $= 1$ | B $12$ | $7 \times 10 ^ 4$ | $= 2$ | B $13$ | $7 \times 10 ^ 4$ | $= 3$ | B $14$ | $7 \times 10 ^ 4$ | $= 3$ | B $15$ | $7 \times 10 ^ 4$ | $= 1$ | 无 $16$ | $7 \times 10 ^ 4$ | $= 2$ | 无 $17$ | $7 \times 10 ^ 4$ | $= 3$ | 无 $18$ | $2 \times 10 ^ 5$ | $= 1$ | 无 $19$ | $2 \times 10 ^ 5$ | $= 2$ | 无 $20$ | $2 \times 10 ^ 5$ | $= 3$ | 无 A：任意时刻所有 $b_i = 1$。 B：无操作二。 --------------------- **【提示】** 样例二满足A类性质，样例三满足B类性质。