F. Product of Sorting Powers

Problem Description

Given a sequence $A$ of length $n$. There are $m$ queries, each given $l, r$, let $B_1, B_2, \dots, B_{r - l + 1}$ as the result of sorting $A_l, A_{l + 1}, \dots, A_r$, calculate:

$$\left(\prod_{i = 1} ^ {r - l} {B_i} ^ {B_{i + 1}} \right) \bmod {(10 ^ 9 + 7)} $$

Input

The first line of the input contains two integers $n, m$ ($1 \le n \le 10 ^ 6$, $1 \le m \le 5000$) - the length of $A$ and the number of queries. The second line contains $n$ integers $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^9$). Each of the following $m$ lines contains two integers $l, r$ ($1 \le l \le r \le n$).

Output

For each query, print a single integer - the answer of the query, modulo $10 ^ 9 + 7$.

Sample Input

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

Sample Output

588255953
426219106
12500000
575819351
16793812

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）