Рассмотрим последовательность \(A_1,A_2,\ldots,A_N\) длины \(N\)
\((1\le N\le 5\cdot 10^4)\), состоящую только из целых чисел в диапазоне
\(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\).
Неубывающая подпоследовательность of \(A_L,\ldots,A_R\) есть коллекция
индексов \((j_1,j_2,\ldots, j_x)\) таких что \(L\le j_1<j_2<\cdots<j_x\le R\) и
\(A_{j_1}\le A_{j_2}\le \cdots \le A_{j_x}.\) Не забудьте рассмотреть пустую
последовательность!
ОЦЕНИВАНИЕ:
- В тестах 2-3 \(N\le 1000\).
- В тестах 4-6 \(K\le 5.\)
- В тестах 7-9 \(Q\le 10^5.\)
- В тестах 10-12 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл nondec.in):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(K\).
Вторая строка содержит \(N\) разделённых пробелом целых числа \(A_1,A_2,\ldots, A_N\).
Третья строка содержит целое число \(Q.\)
Каждая из последующих \(Q\) строк содержит два разделённых пробелом целых числа
\(L_i\) и \(R_i.\)
ФОРМАТ ВЫВОДА (файл nondec.out):
Для каждого запроса \([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
|
3
4
20
|