You are given array $A$ of $n$ integers, initially $0$.
There are $q$ queries of the either form:
- `1 l r x y`: increasing $A_i$ by $(i - l) \times x+y$ for $l \le i \le r$.
- `2 l r`: find the sum of subarray $A_l,A_{l+1},...,A_r$.
### Input
- The first line contains 2 integers $n, q$.
- The next $q$ lines, each line contains either 5 (for type $1$) or 3 (for type $2$) integers, a query.
### Output
- Print the answer for each query of type $2$, modulo $10^9+7$.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le l, r \le n$.
- $1 \le A_i, x, y \le 10^9$.
### Example
Input:
```
5 4
1 1 3 2 1
2 3 5
1 3 4 1 3
2 1 4
```
Output:
```
5
16
```
