Non-Decreasing Subsequences

Input

The first line contains two integers $n (1 \leq n \leq 5 \cdot 1 0^{4})$ n~(1 \le n \le 5 \cdot 10^4) and $k (1 \leq k \leq 20)$ k~(1 \le k \le 20).

The second line contains $n$ integers $A_{1}, A_{2}, \dots, A_{n}$ A_1, A_2, \ldots, A_n.

The third line contains a single integer $q (1 \leq q \leq 2 \cdot 1 0^{5})$ q~(1 \le q \le 2 \cdot 10^5). Each of the next $q$ lines contains two integers $l_{i}$ l_i and $r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ r_i~(1 \le l_i \le r_i \le n).

Output

For each query $[l_{i}, r_{i}]$ [l_i, r_i], print the number of non-decreasing subsequences of $A_{l_{i}}, A_{l_{i} + 1}, \dots, A_{r_{i}}$ A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}, modulo $1 0^{9} + 7$ 10^9 + 7, on a new line.

Examples

For the first query, the non-decreasing subsequences are $(), (2)$ , and $(3)$ . The subsequence $(2, 3)$ is not non-decreasing because $A_{2} > A_{3}$ A_2 > A_3.

For the second query, the non-decreasing subsequences are $(), (4), (5)$ (), (4), (5), and $(4, 5)$ .

Example 1

Loading