Неубывающие подпоследовательности
Бесси недавно участвовала в конкурсе USACO и столкнулась со следующей задачей. Конечно, Бесси знает, как ее решить. А ты?
Рассмотрим последовательность A[1], A[2], ..., A[n] длины n, состоящую только из целых чисел в диапазоне 1...k. Вам даются q (1 ≤ q ≤ 2 * 10^5) запросов вида [l[i], r[i]] (1 ≤ l[i] ≤ r[i] ≤ n). Для каждого запроса вычислите количество неубывающих подпоследовательностей A[li], A[li+1],..., A[ri] по модулю 10^9 + 7.
Неубывающая подпоследовательность A[l],..., A[r] представляет собой такой набор индексов (j[1], j[2], ..., j[x]) что l ≤ j[1] < j[2] < ... < j[x] ≤ r и A[j1] ≤ A[j2] ≤ ... ≤ A[jx]. Обязательно учитывайте пустую подпоследовательность!
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 5 * 10^4) и k (1 ≤ k ≤ 20). Вторая строка содержит n целых чисел A[1], A[2], ..., A[n]. Третья строка содержит одно целое число q. Каждая из следующих q строк содержит по два целых числа l[i] и r[i].
Выходные данные
Для каждого запроса [l[i], r[i]] следует вывести в отдельной строке количество неубывающих подпоследовательностей A[li], A[li+1],... , A[ri] по модулю 10^9 + 7.
Пример
Для первого запроса неубывающими подпоследовательностями являются (), (2) и (3). (2, 3) не является неубывающей подпоследовательностью, так как A[2] > A[3].
Для второго запроса неубывающими подпоследовательностями будут (), (4), (5) и (4, 5).