Non-Decreasing Subsequences

Bessie was recently taking a USACO contest and encountered the following problem. Of course, Bessie knows how to solve it. But do you?

Consider a sequence $A_{1}, A_{2}, \dots, A_{N}$ of length $N$ $(1 \leq N \leq 5 \cdot 1 0^{4})$ consisting solely of integers in the range $1 \dots K$ $(1 \leq K \leq 20) .$ You are given $Q$ ( $1 \leq Q \leq 2 \cdot 1 0^{5}$ ) queries of the form $[L_{i}, R_{i}]$ $(1 \leq L_{i} \leq R_{i} \leq N) .$ For each query, compute the number of non-decreasing subsequences of $A_{L_{i}}, A_{L_{i} + 1} \dots, A_{R_{i}}$ mod $1 0^{9} + 7$ .

A non-decreasing subsequence of $A_{L}, \dots, A_{R}$ is a collection of indices $(j_{1}, j_{2}, \dots, j_{x})$ such that $L \leq j_{1} < j_{2} < \dots < j_{x} \leq R$ and $A_{j_{1}} \leq A_{j_{2}} \leq \dots \leq A_{j_{x}} .$ Make sure to consider the empty subsequence!

SCORING:

Test cases 2-3 satisfy $N \leq 1000$ .
Test cases 4-6 satisfy $K \leq 5.$
Test cases 7-9 satisfy $Q \leq 1 0^{5} .$
Test cases 10-12 satisfy no additional constraints.

For the first query, the non-decreasing subsequences are $(), (2),$ and $(3) .$ $(2, 3)$ is not a non-decreasing subsequence because $A_{2} \neq \leq A_{3} .$

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

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains two space-separated integers $N$ and $K$ .

The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

The third line contains a single integer $Q .$

The next $Q$ lines each contain two space-separated integers $L_{i}$ and $R_{i} .$

Output Format

For each query $[L_{i}, R_{i}],$ you should print the number of non-decreasing subsequences of $A_{L_{i}}, A_{L_{i} + 1} \dots, A_{R_{i}}$ mod $1 0^{9} + 7$ on a new line.

Sample Input

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

Sample Output

3 4 20

Submit

Language