You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

出题人并没有能力写有趣的题面……

题目描述

对于一个长度为 $n$ 的序列 $a_1,a_2,a_3\cdots a_n$，我们定义它的平均数 $a$ 为:

并定义它的方差 $d$ 为:

现在给定一个长度为 $n$ 的序列 $b_1,b_2\cdots b_n$。你需要支持两种操作。每种操作的格式为 c x y。

若 $c=1$，为修改操作，代表将 $b_x$ 赋值为 $y$。

若 $c=2$，为查询操作，代表查询 $b_x$ 到 $b_y$ 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对 $1000000007$（$10^9+7$）取模）。

输入格式

第一行两个整数 $n,m$，代表序列 $b$ 的长度为 $n$，有 $m$ 个操作。

第二行 $n$ 个整数 $b_i$，表示序列 $b$ 的初始值。

下面有 $m$ 行整数，每行格式为 c x y，含义如上文所示。保证所有操作合法。

输出格式

对于每个操作 2，输出一行。

4 8
0 0 0 0
1 1 1
1 2 2
1 3 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4

0
250000002
666666672
250000003

提示

样例 1 解释

四次修改后，序列 $b$ 为：$\{1,2,3,4\}$。

区间 $[1,1]$ 的方差为 $0$。

区间 $[1,2]$ 的方差为 $\frac{1}{4}$ 。$4$ 的逆元为 $250000002$。

区间 $[1,3]$ 的方差为 $\frac{2}{3}$。$3$ 的逆元为 $333333336$，$2\times333333336\bmod M=666666672$。

数据规模与约定

• 对于 $50\%$ 的数据，$n\leq 1000$，$m\leq 1000$。
• 对于 $100\%$ 的数据，$1\leq n,m\leq 1\times 10^5$，$0\leq b_i\leq 1\times 10^9$，$1\leq x\leq n$。对于操作 1，$0\leq y\leq 1\times 10^9$。对于操作2，$x\leq y\leq n$。