Точное покрытие
3000 мс · 256 МБ · всё или ничего
Даны элементов и наборов. Сколькими способами можно выбрать несколько наборов так, чтобы каждый элемент оказался ровно в одном выбранном? Ответ по модулю .
Отличие от задачи о покрытии — слово «ровно»: наборы обязаны быть попарно непересекающимися.
Формат ввода
В первой строке и (, ). В каждой из следующих строк — сначала (), затем различных номеров элементов от 1 до . Наборы могут повторяться и считаются различными.
Формат вывода
Выведите количество точных покрытий по модулю .
Примеры
ввод
2 2 1 1 1 2
вывод
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.