В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».
Давным-давно в далекой галактике существовала планетная система, состоящая из планет. Каждую планету этой системы можно представить как точку с целыми неотрицательными координатами в -мерном пространстве, таким образом, каждая планета имеет координат.
Обозначим за - -ю координату -й планеты.
Известно, что для каждой планеты выполнено неравенство по всем . Иными словами, -я координата любой планеты строго меньше некоторого значения .
Так же известно, что в системе не существует планет с совпадающими координатами.
Находясь на планете , можно совершить прямой перелет на другую планету , если и только если каждая координата планеты не превосходит соответствующей координаты планеты . Более формально, с планеты можно совершить прямой перелет на планету , если для всех от 1 до выполнено неравенство: .
В системе есть обитаемых планет, имеющих номера , все остальные планеты считаются необитаемыми.
Назовем последовательность планет путем, если для каждого можно напрямую перелететь с планеты на планету . Два пути будем считать различными, если последовательности планет в них отличаются.
Император галактики просит вас для каждой планеты от до посчитать количество различных путей, начинающихся в этой планете и заканчивающихся в некоторой обитаемой планете по модулю .
В первой строке вводится число - количество планетных систем, для которых нужно найти ответ.
Описание каждой планетной системы начинается с трех чисел , разделенных пробелом.
В следующей строке содержатся числа - ограничения на координаты планет.
Гарантируется, что во всех тестах данной задачи .
Далее следуют строк, описывающих координаты планет.
-я из следующих строк описывает координаты -й планеты и содержит целые числа
Далее следует строка, содержащая различных чисел - номера обитаемых планет .
Для каждой из планетных систем для каждой планеты в системе выведите количество искомых путей по модулю .
Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).
За каждую планетную систему, для которой был найден правильный ответ, начисляется 2 балла.