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}A\_1,A\_2,\backslash ldots,A\_N$ of length $NN$ $(1\le N\le 5\cdot {10}^4)(1\backslash le\; N\backslash le\; 5\backslash cdot\; 10^4)$ consisting solely of integers in the range $1\dots K1\backslash ldots\; K$ $(1\le K\le 20)\mathrm{.}(1\backslash le\; K\backslash le\; 20).$ You are given $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5$) queries of the form $[L_i,R_i][L\_i,R\_i]$ $(1\le L_i\le R_i\le N)\mathrm{.}(1\backslash le\; L\_i\backslash le\; R\_i\backslash le\; N).$ For each query, compute 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\}\backslash ldots,\; A\_\{R\_i\}$ mod ${10}^9+710^9+7$.

A non-decreasing subsequence of $A_L,\dots ,A_{R}A\_L,\backslash ldots,A\_R$ is a collection of indices $(j_1,j_2,\dots ,j_x)(j\_1,j\_2,\backslash ldots,\; j\_x)$ such that and $A_{j_1}\le A_{j_2}\le \cdots \le A_{j_x}\mathrm{.}A\_\{j\_1\}\backslash le\; A\_\{j\_2\}\backslash le\; \backslash cdots\; \backslash le\; A\_\{j\_x\}.$ Make sure to consider the empty subsequence!

입력

The first line contains two space-separated integers $NN$ and $KK$.

The second line contains $NN$ space-separated integers $A_1,A_2,\dots ,A_{N}A\_1,A\_2,\backslash ldots,\; A\_N$.

The third line contains a single integer $Q\mathrm{.}Q.$

The next $QQ$ lines each contain two space-separated integers $L_{i}L\_i$ and $R_i\mathrm{.}R\_i.$

출력

For each query $[L_i,R_i],[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}A\_\{L\_i\},A\_\{L\_i+1\}\backslash ldots,\; A\_\{R\_i\}$ mod ${10}^9+710^9+7$ on a new line.

힌트

For the first query, the non-decreasing subsequences are $(),(2),(),\; (2),$ and $(3)\mathrm{.}(3).$ $(2,3)(2,3)$ is not a non-decreasing subsequence because $A_2\le ̸A_3\mathrm{.}A\_2\backslash not\; \backslash le\; A\_3.$

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

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

3
4
20