Задача Разбиения

Описание

Разбиением множества S = {1,2,..., n } называется набор P множеств P = { P ₁ , P ₂ , ..., P _k }, такой что U P _i = S и P _i ∩ P _j = ∅ для i != j. Примером разбиения для n = 5 может служить P ₁ = {1,3}, P ₂ = {2,4,5}.

Говорят, что разбиение избегает множество Q если ни одно из множеств P _i не содержит Q в качестве подмножества. Например, разбиение, приведенное выше, избегает множеств {1,2} и {3,4}, но не избегает, например, множеств {1,3} и {2}.

По заданному n и набору множеств Q ₁ , Q ₂ ,..., Q _l найдите количество разбиений, которые избегают каждое из множеств Q _i .

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

Первая строка входного файла содержит два целых числа n и l (1 <= n <= 100, 0 <= l <= 10). Следующие l строк описывают множества, которые следует избегать. Каждая строка начинается с целого числа q _i - размера множества, за которым следует q _i чисел - элементы множеств Q _i .

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

Выведите одно целое число - количество разбиений, которые избегают каждого из множеств Q _i .