Average Counting Problem

You are given an array $A = [A_0, \dots, A_{N−1}]$ consisting of $N$ non-negative integers. You need to process $Q$ queries, each of one of the following two types:

• $1\ l\ r\ val$: Assign the value $val$ to each element $A_l, A_{l+1}, \dots , A_r$.
• $2\ l\ r$: Let $A'$ be the subarray $A[l, r]$, i.e., ${A'}_i = A_{l+i}$ for each $i = 0, \dots , r − l$. Consider the set $S$ of all arrays $B$ of length $r − l + 1$ such that $0 \leq B_i \leq {A'}_i$ for all $0 \leq i \lt r − l + 1$. Compute the sum of all contiguous subarrays of all arrays in $S$, and output the result modulo ${10}^{9} + 7$.

Input data

The first line contains two integers $N$ and $Q$ – the size of the array $A$ and the number of queries, respectively.

The second line contains $N$ integers, representing the elements of the array $A$.

Each of the next $Q$ lines describes a query, either in the form $1\ l\ r\ val$ or $2\ l\ r$.

Output data

For each query of type $2$, print the computed sum on a separate line, modulo ${10}^{9} + 7$.

Constraints and clarifications

• $1 \leq N, Q \leq 200\ 000$.
• $0 \leq A_i \leq 1\ 000\ 000\ 000$ for each $i = 0, \dots, N − 1$.
• $0 \leq l \leq r \lt N$ for every query.
• $0 \leq val \leq 1\ 000\ 000\ 000$ for each query of type $1$.

Example 1

stdin

3 5
3 3 3
2 0 0
2 0 1
2 0 2
1 2 2 1
2 0 2

stdout

6
96
960
384

Explanation

In the sample test case:

• In the first query, $A[0, 0] = [3]$. Thus, $S = \{[0], [1], [2], [3]\}$.
  • The sums of all subarrays of all the arrays in $S$ are $0$, $1$, $2$ and $3$ respectively. As such, the answer is $0 + 1 + 2 + 3 = 6$.
• In the second query, $A[0, 1] = [3, 3]$. Thus, $S = \{[0, 0], [0, 1], [0, 2], [0, 3]$, $[1, 0], [1, 1], [1, 2], [1, 3]$, $[2, 0], [2, 1], [2, 2], [2, 3]$, $[3, 0], [3, 1], [3, 2], [3, 3]\}$.
  • The sums of all subarrays of all the arrays in $S$ are $(0 + 0 + 0) + (0 + 1 + 1) + (0 + 2 + 2) + (0 + 3 + 3) + (1 + 1 + 0) + (1 + 2 + 1) + (1 + 3 + 2) + (1 + 4 + 3) + (2 + 2 + 0) + (2 + 3 + 1) + (2 + 4 + 2) + (2 + 5 + 3) + (3 + 3 + 0) + (3 + 4 + 1) + (3 + 5 + 2) + (3 + 6 + 3) = 96$.
• In the third query, $A[0, 2] = [3, 3, 3]$.
• In the fourth query, $A[0, 2] = [3, 3, 1]$.