증가하지 않는 부분수열

수현이는 최근 USACO 대회에 참여하여, 다음과 같은 문제를 마주쳤습니다. 

물론, 수현이는 이 문제를 해결하는 방법을 알고 있습니다. 그렇다면 당신은 어떠신가요?

$A_1, A_2, \ldots, A_N$의 길이가 $N$인 수열을 생각해 보십시오. 

$(1 \le N \le 5 \cdot 10^4)$ 이 수열은 $1 \ldots K$ 범위의 정수만을 포함하고 있습니다. $(1 \le K \le 20)$ 당신은 $[L_i, R_i]$ 형태의 $Q$개의 쿼리를 받게 됩니다. $(1 \le Q \le 2 \cdot 10^5)$ 각 쿼리마다, $A_{L_i}, A_{L_i+1} \ldots, A_{R_i}$ 의 증가하지 않는 부분수열의 수를 $10^9+7$로 나눈 나머지를 계산합니다.

증가하지 않는 $A_L, \ldots, A_R$의 부분수열은 $L \le j_1 \lt j_2 \lt \cdots \lt j_x \le R$ 그리고 $A_{j_1} \le A_{j_2} \le \cdots \le A_{j_x}$를 만족하는 인덱스 $(j_1, j_2, \ldots, j_x)$의 집합입니다. 빈 부분수열도 고려하는 것을 잊지 마십시오!

첫 번째 줄에는 두 개의 공백으로 구분된 정수 $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$로 나눈 나머지를 새로운 줄에 출력합니다.