Планетная система - 1

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

В этой задаче на проверку необходимо сдать исходный код программы.

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

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

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

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

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

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

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

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

Формат ввода

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

Описание каждой планетной системы начинается с трех чисел n , m , k ( 1 n 1 0 5 , 1 m 16 , 0 k n ) 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 q_1, q_2, ..., q_m - ограничения на координаты планет.

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

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

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

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

Формат вывода

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

Система оценивания

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

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

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

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

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

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

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

Пример

ВводВывод
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

Примечания

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

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