Variance Queries with Fraction Modulo Arithmetic

Given a sequence of integers \( b_1, b_2, \ldots, b_n \), you need to support two types of operations:

• 1 x y: Update the value at index \( x \) to \( y \), i.e. set \( b_x = y \).
• 2 x y: Query the variance of the subarray from \( b_x \) to \( b_y \).

For a sequence \( a_1, a_2, \ldots, a_m \), define the average \( a \) and the variance \( d \) as follows:

[ a = \frac{1}{m}\sum_{i=1}^{m}a_i ]

[ d = \frac{1}{m}\sum_{i=1}^{m}(a_i - a)^2 = \frac{m \cdot \sum_{i=1}^{m}a_i^2 - \left(\sum_{i=1}^{m}a_i\right)^2}{m^2} ]

To avoid floating-point errors, output the variance as a fraction \( \frac{p}{q} \) reduced modulo \(10^9+7\). In other words, if the variance is \(\frac{p}{q}\), output \(p \cdot q^{-1} \bmod (10^9+7)\), where \(q^{-1}\) denotes the modular inverse of \(q\) modulo \(10^9+7\).

inputFormat

The first line contains two integers \( n \) and \( q \) — the length of the sequence and the number of operations.

The second line contains \( n \) integers \( b_1, b_2, \ldots, b_n \).

Each of the next \( q \) lines contains an operation in the format c x y. If \( c = 1 \), update the value at index \( x \) to \( y \). If \( c = 2 \), output the variance of the subarray from \( b_x \) to \( b_y \).

outputFormat

For each query operation (where \( c = 2 \)), output a single line with the variance in modulo fraction form, i.e., compute

[ \text{variance} = \frac{m \cdot \text{sum2} - (\text{sum})^2}{m^2} \bmod (10^9+7), ]

where ( m ) is the number of elements in the subarray, ( \text{sum} ) is the sum of the subarray, and ( \text{sum2} ) is the sum of squares of the subarray. The division is performed using the modular inverse of ( m^2 ) modulo ( 10^9+7 ).

sample

3 2
1 2 3
2 1 3
2 2 2

666666672
0