Незменшувані підпослідовності
Бессі нещодавно брала участь у конкурсі 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).