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

Давным-давно в далекой галактике существовала планетная система, состоящая из $$$n$$$ планет. Каждую планету этой системы можно представить как точку с целыми неотрицательными координатами в $$$m$$$-мерном пространстве, таким образом, каждая планета имеет $$$m$$$ координат.

Обозначим за $$$c_{i,j}$$$ - $$$j$$$ -ю координату $$$i$$$ -й планеты.

Известно, что для каждой планеты $$$i(1 \leq i \leq n)$$$ выполнено неравенство $$$0 \leq c_{i, j} < q_j$$$ по всем $$$j(1 \leq j \leq m)$$$. Иными словами, $$$j$$$-я координата любой планеты строго меньше некоторого значения $$$q_j$$$.

Так же известно, что в системе не существует планет с совпадающими координатами.

Находясь на планете $$$a$$$, можно совершить прямой перелет на другую планету $$$b$$$, если и только если каждая координата планеты $$$b$$$ не превосходит соответствующей координаты планеты $$$a$$$. Более формально, с планеты $$$a$$$ можно совершить прямой перелет на планету $$$b$$$, если для всех $$$j$$$ от 1 до $$$m$$$ выполнено неравенство: $$$c_{b, j} \leq c_{a, j}$$$.

В системе есть $$$k$$$ обитаемых планет, имеющих номера $$$x_1, x_2, ..., x_k$$$, все остальные планеты считаются необитаемыми.

Назовем последовательность планет $$$y_1, y_2, ..., y_r$$$ путем, если для каждого $$$i(1 \leq i < r)$$$ можно напрямую перелететь с планеты $$$y_i$$$ на планету $$$y_{i+1}$$$. Два пути будем считать различными, если последовательности планет в них отличаются.

Император галактики просит вас для каждой планеты от $$$1$$$ до $$$n$$$ посчитать количество различных путей, начинающихся в этой планете и заканчивающихся в некоторой обитаемой планете по модулю $$$10^9 + 7$$$.

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

В первой строке вводится число $$$t$$$ - количество планетных систем, для которых нужно найти ответ.

Описание каждой планетной системы начинается с трех чисел $$$n, m, k(1 \leq n \leq 10^5, 1 \leq m \leq 16, 0 \leq k \leq n)$$$, разделенных пробелом.

В следующей строке содержатся числа $$$q_1, q_2, ..., q_m$$$ - ограничения на координаты планет.

Гарантируется, что во всех тестах данной задачи $$$\prod_{j=1}^m q_j \leq 10^5$$$.

Далее следуют $$$n$$$ строк, описывающих координаты планет.

$$$i$$$-я из следующих $$$n$$$ строк описывает координаты $$$i$$$-й планеты и содержит целые числа $$$c_{i, 1}, c_{i, 2}, ..., c_{i, m}(0 \leq c_{i, j} < q_j)$$$.

Далее следует строка, содержащая $$$k$$$ различных чисел - номера обитаемых планет $$$x_1, x_2, ..., x_k(1 \leq x_i \leq n)$$$.

За каждую планетную систему, для которой был найден правильный ответ, начисляется 2 балла.

В первом тесте 3 планетных системы, в каждой из них не более 20 планет.

Во втором тесте 5 планетных систем, в каждой из них не более 2000 планет.

В третьем тесте 2 планетные системы, в каждой из них $$$m = 1$$$.

В четвертом тесте 5 планетных систем, в каждой из них $$$m = 2$$$.

В пятом тесте 10 планетных систем, дополнительных ограничений нет.

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

Для каждой из $$$t$$$ планетных систем для каждой планеты в системе выведите количество искомых путей по модулю $$$10^9 + 7$$$.

Пример

Входные данные
2
2 2 1
2 2
0 0
0 1
2
3 2 2
2 2
0 0
0 1
1 0
1 2
Выходные данные
0
1
1
2
1

Примечание

Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).

В первой планетной системе две планеты, первая планета имеет координаты $$$(0, 0)$$$, вторая планета имеет координаты $$$(0, 1)$$$, планета 2 является единственной обитаемой планетой. Первая планета необитаема, и с нее нельзя никуда перелететь, поэтому количество путей, начинающихся в этой планете и заканчивающихся в обитаемой планете, равно $$$0$$$. Вторая планета обитаема, поэтому путь, состоящий лишь из нее, нам подходит, в то же время путь $$$2 \rightarrow 1$$$ оканчивается в необитаемой планете, следовательно, нам не подходит. Таким образом, ответ для второй планеты равен 1.

Во второй планетной системе три планеты, первая имеет координаты $$$(0, 0)$$$, вторая планета имеет координаты $$$(0, 1)$$$, третья планета имеет координаты $$$(1, 0)$$$. Планеты $$$1$$$ и $$$2$$$ являются обитаемыми. Из первой планеты перелететь никуда нельзя, но можно остаться на ней и получить путь, состоящий лишь из первой планеты, которая является обитаемой, следовательно, этот путь подходит нам. Для второй планеты существуют пути $$$2 \rightarrow 1$$$, так как планета $$$1$$$ обитаема, а так же путь, состоящий лишь из второй планеты, поэтому ответ для этой планеты $$$2$$$. Для третьей планеты существует лишь один путь $$$3 \rightarrow 1$$$, заканчивающийся в первой планете, которая является обитаемой, следовательно, ответ для третьей планеты $$$1$$$.