EduBrick

Точное покрытие

3000 мс · 256 МБ · всё или ничего

Даны nn элементов и mm наборов. Сколькими способами можно выбрать несколько наборов так, чтобы каждый элемент оказался ровно в одном выбранном? Ответ по модулю 109+710^9 + 7.

Отличие от задачи о покрытии — слово «ровно»: наборы обязаны быть попарно непересекающимися.

Формат ввода

В первой строке nn и mm (1≤n≤161 \le n \le 16, 1≤m≤1051 \le m \le 10^5). В каждой из следующих mm строк — сначала kik_i (0≤ki≤n0 \le k_i \le n), затем kik_i различных номеров элементов от 1 до nn. Наборы могут повторяться и считаются различными.

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

Выведите количество точных покрытий по модулю 109+710^9 + 7.

Примеры

ввод
2 2
1 1
1 2
вывод
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.