P6009 [USACO20JAN] Non-Decreasing Subsequences P

Bessie recently took part in a USACO contest and encountered the following problem. Of course, Bessie knows how to solve it. Do you? Consider a sequence of length $N$, $A_1, A_2, \ldots, A_N$, consisting only of integers in the range $1 \ldots K$ ($1 \leq K \leq 20$) ($1 \leq N \leq 5 \times 10^4$). You are given $Q$ ($1 \leq Q \leq 2 \times 10^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 in $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ modulo $10^9+7$. A non-decreasing subsequence of $A_L, \ldots, A_R$ is a sequence of indices $(j_1, j_2, \ldots, j_x)$ such that $L \le j_1 < j_2 < \ldots < j_x \le R$ and $A_{j_1} \le A_{j_2} \le \ldots \le A_{j_x}$. Make sure you also count the empty subsequence.

The first line contains two space-separated integers $N$ and $K$. The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. The third line contains an integer $Q$. The next $Q$ lines each contain two space-separated integers $L_i$ and $R_i$.

For each query $[L_i, R_i]$, output on a new line the number of non-decreasing subsequences in $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ modulo $10^9+7$.

### Sample Explanation For the first query, the non-decreasing subsequences are $()$, $(2)$, and $(3)$. $(2,3)$ is not a non-decreasing subsequence because $A_2\not \le A_3$. For the second query, the non-decreasing subsequences are $()$, $(4)$, $(5)$, and $(4,5)$. ### Subtasks - Test points $2 \sim 3$ satisfy $N \leq 1000$. - Test points $4 \sim 6$ satisfy $K \leq 5$. - Test points $7 \sim 9$ satisfy $Q \leq 10^5$. - Test points $10 \sim 12$ have no additional constraints. Translated by ChatGPT 5