Розглянемо послідовність \(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 немає додаткових обмежень.

Формат вхідних даних

Перший рядок містить два розділені пропуском цілих числа \(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\).

Приклад вхідних даних

5 2
1 2 1 1 2
3
2 3
4 5
1 5

Приклад вихідних даних

3
4
20

Для першого запиту, неспадні підпослідовності такі: \((), (2),\) і \((3).\) \((2,3)\) не є неспадною підпослідовністю, оскільки \(A_2\not \le A_3.\)

Для другого запиту, неспадні підпослідовності такі: \(()\), \((4)\), \((5)\), (4,5)~.