### 问题描述 小齐最近参加了一场算法比赛，并遇到了以下问题。当然，小齐知道如何解决它。那么，你知道吗？ 考虑一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$，由范围在 $1$ 到 $K$ 之间的整数组成。给定 $Q$ 个形如 [Li, Ri] 的查询。对于每个查询，计算模 $10^9+7$ 下 $A_{Li}, A_{Li+1}, \ldots, A_{Ri}$ 的非递减子序列的数量。 非递减子序列是指索引集合 $(j_1, j_2, \ldots, j_x)$，使得 $L \leq j_1 < j_2 < \ldots < j_x \leq R$ 且 $A_{j_1} \leq A_{j_2} \leq \ldots \leq A_{j_x}$。请确保考虑到空子序列！ ### 输入格式 第一行包含两个用空格分隔的整数 $N$ 和 $K$。 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \ldots, A_N$。 第三行包含一个整数 $Q$。 接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $Li$ 和 $Ri$。 ### 输出格式 对于每个查询 $[Li, Ri]$，在新的一行上输出 $A_{Li}, A_{Li+1}, \ldots, A_{Ri}$ 的非递减子序列数量，取模 $10^9+7$。 ### 样例输入 ``` 5 2 1 2 1 1 2 3 2 3 4 5 1 5 ``` ### 样例输出 ``` 3 4 20 ``` ### 评测数据规模 $1 \leq N \leq 5 \times 10^4$，$1 \leq K \leq 20$，$1 \leq Q \leq 2 \times 10^5$，$1 \leq Li \leq Ri \leq N$。