Với bài này, chỉ đơn giản là cho một bài toán khá dễ dàng và siêu ngắn gọn như sau:

Cho mảng ~A~ gồn ~n~ phần từ ~a_1~, ~a_2~, ..., ~a_n~.

Cho ~q~ truy vấn, truy vấn thứ ~i~ gồm hai số nguyên dương ~l_i~, ~r_i~ thoả mãn điều kiện ~1 \le l_i \le r_i \le n~. Với mỗi truy vấn ~i~, tính:

$$ \Large \sum_{u=l_i}^{r_i} \sum_{v=u}^{r_i} \sum_{p=u}^{v} a_p $$

Nói cách khác, hãy tính tổng của mọi đoạn con liên tiếp ~[u, v]~ thỏa mãn ~l_i \le u \le v \le r_i~.

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Input

Nhập từ tệp SQP.INP

Dòng thứ nhất chứa hai số nguyên ~n,q~

Dòng tiếp theo là ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^6~ ~\forall i \in [1,n])~

~q~ dòng cuối cùng, dòng thứ ~i~ chứa 2 số nguyên ~l_i,r_i~

Output

Xuất ra tệp SQP.OUT

Gồm ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~

Subtasks

Sample Input

5 4
3 4 1 2 4
1 5
1 3
2 4
3 5

Sample Output

92
28
22
23