[Hidden ☆ before use]

Description

There are n stocks in the market, and after researching, the variance of the i-th stock’s price is a_i per dollar you devoted.
Master Dong is reluctant to taking risk, so he wants to put the money on hand into n shares in a certain proportion, so that the total amount of total investment in all stocks fluctuates to a minimum.
We use the variance as a measure of volatility. We assume the money Master Dong invested into stocks is a real number. And we just define the unit minimum variance (UMV) as the variance of each dollar Mater Dong invested, under the optimal strategy.
There are m days now. For each day we have a cmd.
cmd = 1 indicates that the market was uniformly regulated on that day, and the stock price was adjusted by x % for the stocks from l to r.
cmd = 2 means if only stocks l to r are considered, what is UMA.
It’s guaranteed the answer is a rational number in the form of p/q. You only need to output p × q-1  mod  10^9+7 in order to avoid accuracy error and high precision.
n ≤ 2 × 10^5， m ≤ 2 × 10^5,  1 ≤ di < 10^9, all inputs are integers.

Input

The first line contains two intergers : n, m.
The next line contains n integers a1 ... an
The next m lines: first input cmd, if cmd = 1, input l, r, x, or l ,r

Output

For every cmd = 2, output an integer in a line.

Samples

Input Copy
5 4
1 2 3 4 5
2 1 2
2 1 5
1 2 3 2
2 1 5

Output
666666672
503649639
24407394


Source

Problem Information

 Time Limit: 1000MS (C/C++,Others×2) Memory Limit: 128MB (C/C++,Others×2) Special Judge: No AC/Submit: 1 / 1 Tags:
Contests involved

 1017. 2018 SD ACM