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.
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
For every cmd = 2, output an integer in a line.
1 2 3 4 5
2 1 2
2 1 5
1 2 3 2
2 1 5