Description

For a sequence of length $n$, $a_1,a_2,a_3\cdots a_n$, we define its mean $a$ as:

and define its variance $d$ as:

Now you are given a sequence $b_1,b_2\cdots b_n$ of length $n$. You need to support two operations. Each operation has the format c x y.

If $c=1$, it is an update: set $b_x$ to $y$.

If $c=2$, it is a query: compute the variance of $b_x$ through $b_y$ (inclusive).

To avoid floating-point errors, output the result as a fraction modulo (mod $1000000007$ ($10^9+7$)).

Input Format

The first line contains two integers $n,m$, meaning the sequence $b$ has length $n$ and there are $m$ operations.

The second line contains $n$ integers $b_i$, representing the initial values of sequence $b$.

Then there are $m$ lines, each in the format c x y, with meanings as described above. All operations are guaranteed to be valid.

Output Format

For each operation $2$, output one line.

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

Hint

Explanation for Sample 1

After four updates, the sequence $b$ is: $\{1,2,3,4\}$.

The variance of interval $[1,1]$ is $0$.

The variance of interval $[1,2]$ is $\frac{1}{4}$. The modular inverse of $4$ is $250000002$.

The variance of interval $[1,3]$ is $\frac{2}{3}$. The modular inverse of $3$ is $333333336$, and $2\times333333336\bmod M=666666672$.

Constraints

• For $50\%$ of the testdata, $n\leq 1000$, $m\leq 1000$.
• For $100\%$ of the testdata, $1\leq n,m\leq 1\times 10^5$, $1\leq b_i\leq 1\times 10^9$, $1\leq x\leq n$. For operation $1$, $1\leq y\leq 1\times 10^9$. For operation $2$, $x\leq y\leq n$.

Translated by ChatGPT 5