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

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

Давным-давно в далекой галактике существовала планетная система, состоящая из 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 балла.