E. Подсчет суперпоследовательностей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, в котором все элементы $$$a_i$$$ лежат в диапазоне $$$[1, k]$$$. Сколько различных массивов $$$b$$$ из $$$m$$$ целых чисел, где все элементы $$$b_i$$$ лежат в диапазоне $$$[1, k]$$$, содержат $$$a$$$ в качестве подпоследовательности? Два массива считаются различными, если они отличаются хотя бы в одной позиции.

Последовательность $$$x$$$ является подпоследовательностью последовательности $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ путем удаления нескольких (возможно, нуля или всех) элементов.

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

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$n \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$) — размер $$$a$$$, размер $$$b$$$ и максимально допустимое значение в массивах, соответственно.

Следующая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1\le a_i \le k$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2\cdot 10^5$$$.

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

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

Пример
Входные данные
7
1 1000000 1
1
3 4 3
1 2 2
5 7 8
1 2 3 4 1
6 6 18
18 2 2 5 2 16
1 10 2
1
8 10 1234567
1 1 2 1 2 2 2 1
5 1000000000 1000000000
525785549 816356460 108064697 194447117 725595511
Выходные данные
1
9
1079
1
1023
906241579
232432822
Примечание

В первом примере, поскольку $$$k=1$$$, существует только один массив размера $$$m$$$, состоящий из целых чисел $$$[1, k]$$$. Этот массив ($$$[1, 1, \ldots, 1]$$$) содержит исходный массив в качестве подпоследовательности, поэтому ответ - 1.

Во втором примере есть $$$9$$$ массивов: $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[1, 2, 2, 3]$$$, $$$[1, 2, 3, 2]$$$, $$$[1, 3, 2, 2]$$$, $$$[2, 1, 2, 2]$$$, $$$[3, 1, 2, 2]$$$.

В четвертом примере, поскольку $$$m=n$$$, единственным массивом размера $$$m$$$, который содержит $$$a$$$ в качестве подпоследовательности, является сам $$$a$$$.