E. Очередная задача на подсчёт массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Позиция первого максимума на отрезке $$$[l; r]$$$ массива $$$x = [x_1, x_2, \ldots, x_n]$$$ это наименьшее целое число $$$i$$$, такое что $$$l \le i \le r$$$ и $$$x_i = \max(x_l, x_{l+1}, \ldots, x_r)$$$.

Вам дан массив $$$a = [a_1, a_2, \ldots, a_n]$$$ длины $$$n$$$. Найдите количество массивов $$$b = [b_1, b_2, \ldots, b_n]$$$ длины $$$n$$$, удовлетворяющих следующим требованиям:

  • $$$1 \le b_i \le m$$$ для всех $$$1 \le i \le n$$$;
  • для всех пар $$$1 \le l \le r \le n$$$, позиция первого максимума на отрезке $$$[l; r]$$$ массива $$$b$$$ равна позиции первого максимума на отрезке $$$[l; r]$$$ массива $$$a$$$.

Так как это количество может быть очень большим, выведите его по модулю $$$10^9+7$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке даны два числа $$$n$$$ и $$$m$$$ ($$$2 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 10^6$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите одно число: количество массивов $$$b$$$, удовлетворяющих требованиям выше, по модулю $$$10^9+7$$$.

Пример
Входные данные
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60
Выходные данные
8
5
11880
351025663
Примечание

В первом наборе входных данных следующие $$$8$$$ массивов удовлетворяют требованиям из условия:

  • $$$[1,2,1]$$$;
  • $$$[1,2,2]$$$;
  • $$$[1,3,1]$$$;
  • $$$[1,3,2]$$$;
  • $$$[1,3,3]$$$;
  • $$$[2,3,1]$$$;
  • $$$[2,3,2]$$$;
  • $$$[2,3,3]$$$.

Во втором наборе входных данных следующие $$$5$$$ массивов удовлетворяют требованиям из условия:

  • $$$[1,1,1,1]$$$;
  • $$$[2,1,1,1]$$$;
  • $$$[2,2,1,1]$$$;
  • $$$[2,2,2,1]$$$;
  • $$$[2,2,2,2]$$$.