Bessie 最近参加了一场 USACO 比赛，遇到了下面这道题。当然，Bessie 知道怎么解决它。但你呢？

考虑一个长度为 $N$ $(1\le N\le 5\cdot 10^4)$ 的序列 $A_1,A_2,\ldots,A_N$，其中仅包含 $1\ldots K$ $(1\le K\le 20)$ 范围内的整数。给定 $Q$ $(1\le Q\le 2\cdot 10^5)$ 个查询，每个查询的形式为 $[L_i,R_i]$ $(1\le L_i\le R_i\le N)$。对于每个查询，计算 $A_{L_i},A_{L_i+1}\ldots, A_{R_i}$ 的非递减子序列的数量，结果对 $10^9+7$ 取模。

$A_L,\ldots,A_R$ 的非递减子序列是指一组下标 $(j_1,j_2,\ldots, j_x)$，满足 $L\le j_1

子任务

• 测试点 2-3 满足 $N\le 1000$。
• 测试点 4-6 满足 $K\le 5$。
• 测试点 7-9 满足 $Q\le 10^5$。
• 测试点 10-12 满足无额外限制。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$。

第二行包含 $N$ 个空格分隔的整数 $A_1,A_2,\ldots, A_N$。

第三行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含两个空格分隔的整数 $L_i$ 和 $R_i$。

输出格式

对于每个查询 $[L_i,R_i]$，请在单独的一行中输出 $A_{L_i},A_{L_i+1}\ldots, A_{R_i}$ 的非递减子序列数量，结果对 $10^9+7$ 取模。

样例

样例输入 1

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

样例输出 1

3
4
20

说明

对于第一个查询，非递减子序列为 $()$，$ (2)$ 和 $(3)$。$(2,3)$ 不是非递减子序列，因为 $A_2\not \le A_3$。

对于第二个查询，非递减子序列为 $()$，$ (4)$，$ (5)$ 和 $(4,5)$。

题目来源：Benjamin Qi