408885: GYM103371 M Yet Another Range Query Problem

You are given an array $$$A$$$, consisting of distinct integers in the range $$$1, 2, \ldots, n$$$.

Let $$$B$$$ be an $$$n \times n$$$ matrix, where $$$B_{i, j} = \min(A_i, \ldots, A_j) \times \max(A_i, \ldots, A_j)$$$ if $$$i \leq j$$$. Otherwise, $$$B_{i, j} = 0$$$.

Given $$$q$$$ queries of the form $$$l, r, s, e$$$, please compute the value $$$\sum_{x = l}^{r}\sum_{y = s}^{e} B_{x, y}$$$ modulo $$$10^9 + 7$$$.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 150\,000$$$).

The next line contains $$$n$$$ distinct integers $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \le A_i \le n$$$).

The next $$$q$$$ lines each contain four integers $$$l, r, s, e$$$, the $$$i$$$-th such line denoting the parameters of the $$$i$$$-th query. ($$$1 \le l \le r \le n, 1 \le s \le e \le n$$$).

Output $$$q$$$ lines. On the $$$i$$$-th line, output the answer of the $$$i$$$-th query.

10 10
7 6 1 10 5 3 2 4 8 9
1 2 7 8
7 9 8 8
2 10 8 8
5 10 1 4
7 9 2 9
1 7 8 10
3 8 5 9
3 10 2 6
1 4 4 8
1 3 1 5

40
24
82
0
140
278
381
260
370
201