В этой задаче на проверку необходимо сдать текстовый файл, соответствующий формату вывода.
Давным-давно в далекой галактике существовала планетная система, состоящая из $$$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 балла.
Для каждой из $$$t$$$ планетных систем для каждой планеты в системе выведите количество искомых путей по модулю $$$10^9 + 7$$$.
22 2 12 20 00 123 2 22 20 00 11 01 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$$$.