RMQ

길이 $N$의 수열 $A$가 주어진다. 각 원소는 $1$ 이상 $N$ 이하의 정수이고, 같은 값은 한 번만 나온다.

수열 $A$에 대한 RMQ는 보통 Range Minimum Query 또는 Range Maximum Query를 뜻한다. $1 \le l \le r \le N$인 $l$과 $r$이 주어졌을 때 $\min(A_l, \cdots, A_r)$ 또는 $\max(A_l, \cdots, A_r)$를 구하는 쿼리이다.

어떤 쿼리도 포기하지 못하는 종영이는 새로운 RMQ를 만들기로 했다. 종영이가 만든 RMQ(Range Mueonga Query)는 $RMQ(l,r)=\min(A_l, \cdots, A_r) \times \max(A_l, \cdots, A_r)$이다.

모든 쿼리 값을 기억하려고 $N$행 $N$열의 2차원 배열 $B$를 만들었다. $i$행 $j$열의 값 $B_{i,j}$는 $i \le j$이면 $RMQ(i,j)$이고, $i>j$이면 $0$이다.

쿼리 중독증이 있는 종영이는 이제 $B$에 대해 2차원 쿼리를 날리고 싶어졌다. $1 \le l \le r \le N$이고 $1 \le s \le e \le N$인 정수 네 개 $l$, $r$, $s$, $e$가 주어질 때마다, $l \le i \le r$이고 $s \le j \le e$인 모든 $i$, $j$에 대해 $B_{i,j}$의 합을 구하자.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 150\,000$, $1 \le Q \le 150\,000$)

둘째 줄에 $A_1, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le N$)

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 공백으로 구분된 $l$, $r$, $s$, $e$로 이루어진다. ($1 \le l \le r \le N$, $1 \le s \le e \le N$)

각 쿼리의 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.