Диппер и Мэйбл решили еще раз обследовать Гравити Фолз. Надо сказать, что Гравити Фолз не сильно отличается по общему устройству от других городов — он также представляет из себя совокупность домов, соединенных улицами. Причем для каждой пары домов существует не более одной улицы их соединяющей. Да и петель, то есть улиц, соединяющих дом с самим собой, тоже нет. Также известно, что если по улице можно добраться от дома А до дома В, то и от дома В до дома А можно добраться по этой же улице.
Сейчас Диппер и Мэйбл решили составить список маршрутов, которые бы посещали каждый дом ровно один раз. (То есть если в городе n домов, то в маршруте будет ровно n различных чисел — номеров домов, и между любыми двумя соседними будет существовать одна улица). Диппер и Мэйбл считают два маршрута разными, если в них разные последовательности домов.
Список оказался довольно большим. К тому же Диппер и Мэйбл не уверены, что он правильный. Для того чтобы проверить выкладки, они хотели бы для начала знать количество таких путей. Без Вас им точно не обойтись!
В первой строке входного файла дано натуральное число n — количество домов (1 ≤ n ≤ 1000). Далее следуют n строк. Каждая i-ая строка задана в следующем формате: первое число в строке k — число соседних (то есть связанных улицей) домов для i-го дома, далее перечислены k различных чисел — номера соседних с i-ым домов.
Выведите одно число — количество вышеописанных маршрутов. Поскольку данное число может быть довольно большим, выведите его по модулю 2.
5
3 2 3 5
3 1 3 4
4 1 2 4 5
3 2 3 5
3 1 3 4
0