E2. Прайм Гейминг (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$m \le 10^6$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Валидной является такая конфигурация $$$n$$$ кучек камней, в которой:

  • Количество камней в каждой кучке — это целое число от $$$1$$$ до $$$m$$$ (включительно).

Дана валидная конфигурация из $$$n$$$ кучек камней, некоторые индексы от $$$1$$$ до $$$n$$$ помечены как хорошие. Алиса и Боб начинают играть в игру, делая поочередно $$$n-1$$$ ходов, при этом Алиса ходит первой. На каждом ходу они должны выполнить следующую операцию:

  • Выбрать любое целое число $$$i$$$, такое что $$$1 \le i \le p$$$ (где $$$p$$$ — количество оставшихся кучек) и $$$i$$$ является хорошим, и полностью удалить $$$i$$$-ю кучку.

Обратите внимание, что после выполнения операции количество кучек уменьшается на $$$1$$$, и оставшиеся кучки перенумеровываются. Игра закончится, когда останется только одна кучка. Гарантируется, что индекс $$$1$$$ всегда хороший.

Обозначим $$$x$$$ как количество камней в последней оставшейся кучке. Алиса хочет максимизировать $$$x$$$, в то время как Боб хочет минимизировать его. Оба игрока играют оптимально.

Найдите сумму $$$x$$$ по всем возможным валидным конфигурациям по модулю $$$10 ^ 9 + 7$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ ($$$1 \le n \le 20$$$) и $$$m$$$ ($$$1 \le m \le 10^6$$$) — количество кучек и верхнее ограничение на количество камней в кучке.

Вторая строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$1 \le k \le n$$$) — количество индексов, помеченных как хорошие.

Третья строка каждого набора входных данных содержит $$$k$$$ целых чисел $$$c_1,c_2,\ldots,c_k$$$ ($$$1=c_1 \lt c_2 \lt \ldots \lt c_k\le n$$$) — хорошие индексы. Гарантируется, что $$$1$$$ всегда является хорошим индексом (т.е. $$$c_1=1$$$).

Гарантируется, что сумма значений $$$2^n$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.

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

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

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

Пример
Входные данные
5
2 3
1
1
7 4
3
1 4 6
12 31
6
1 3 5 7 9 11
11 121
11
1 2 3 4 5 6 7 8 9 10 11
19 6969
2
1 19
Выходные данные
18
33664
909076242
683044824
901058932
Примечание

Для первого набора входных данных валидными конфигурациями являются: $$$[1, 1]$$$, $$$[1,2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$, $$$[2,3]$$$, $$$[3,1]$$$, $$$[3,2]$$$, $$$[3,3]$$$.

Поскольку есть только $$$2$$$ кучки камней, Алиса может выбрать только первую кучку и убрать её. Таким образом, сумма $$$x$$$ равна $$$1+1+1+2+2+2+3+3+3= 18$$$.