Бесси недавно участвовала в конкурсе USACO и столкнулась со следующей задачей. Конечно, Бесси знает, как ее решить. А ты?

Рассмотрим последовательность A1, A2, ..., An длины n, состоящую только из целых чисел в диапазоне 1...k. Вам даются q (1 ≤ q ≤ 2 * 105) запросов вида [li, ri] (1 ≤ li ≤ ri ≤ n). Для каждого запроса вычислите количество неубывающих подпоследовательностей Ali, Ali+1,..., Ari по модулю 109 + 7.

Неубывающая подпоследовательность Al,..., Ar представляет собой такой набор индексов (j1, j2, ..., jx) что l ≤ j1 < j2 < ... < jx ≤ r и Aj1 ≤ Aj2 ≤ ... ≤ Ajx. Обязательно учитывайте пустую подпоследовательность!

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 5 * 104) и k (1 ≤ k ≤ 20). Вторая строка содержит n целых чисел A1, A2, ..., An. Третья строка содержит одно целое число q. Каждая из следующих q строк содержит по два целых числа li и ri.

Выходные данные

Для каждого запроса [li, ri] следует вывести в отдельной строке количество неубывающих подпоследовательностей Ali, Ali+1,... , Ari по модулю 109 + 7.

Пример

Для первого запроса неубывающими подпоследовательностями являются (), (2) и (3). (2, 3) не является неубывающей подпоследовательностью, так как A2 > A3.

Для второго запроса неубывающими подпоследовательностями будут (), (4), (5) и (4, 5).