비감소 부분수열

Bessie는 최근 USACO 대회에 참가했다가 다음 문제를 만났다. 물론 Bessie는 이 문제를 푸는 방법을 알고 있다. 하지만 당신은 알고 있는가?

$1\ldots K$ $(1\le K\le 20)$ 범위의 정수로만 이루어진 길이 $N$ $(1\le N\le 5\cdot 10^4)$의 수열 $A_1,A_2,\ldots,A_N$이 주어진다. $[L_i,R_i]$ $(1\le L_i\le R_i\le N)$ 형태의 쿼리 $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<j_2<\cdots<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$로 나눈 나머지를 새 줄에 출력한다.

첫 번째 쿼리의 비감소 부분수열은 $(), (2), (3)$이다. $(2,3)$은 $A_2\not \le A_3$이므로 비감소 부분수열이 아니다.

두 번째 쿼리의 비감소 부분수열은 $()$, $(4)$, $(5)$, $(4,5)$이다.