В это время года близок фестиваль и вы можете видеть празднующих людей повсюду в Гималаях. В Гималаях есть n школ. Школа i учит gi покемонов. В Гималаях существуют m различных типов покемонов, типы пронумерованы от 1 до m.
На площадке фестиваля организован специальный эволюционный лагерь, в котором каждый покемон может эволюционировать. Тип покемона может измениться после того, как покемон эволюционирует, однако, если два покемона были одного типа до эволюционирования, то они будут одного типа после. Также, если два покемона были различных типов до эволюционирования, то они будут различными и после него. Возможно, что покемон не поменяет свой тип после эволюционирования.
Формально, планом эволюционирования называется перестановка f чисел {1, 2, ..., m}, при этом f(x) = y означает, что покемон типа x эволюционирует в тип y.
Руководители школ заинтригованы специальным лагерем, и все из них хотят эволюционировать всех своих покемонов. Устав Гималаев гласит, что в каждой школе количество покемонов каждого типа до эволюционирования должно быть равно количеству покемонов этого типа после эволюционирования. Руководители хотят найти количество различных планов эволюционирования, удовлетворяющих уставу Гималаев.
Два плана эволюционирования f1 и f2 считаются различными, если как минимум один тип покемонов эволюционирует в разные типы в этих двух планов, то есть существует i такое, что f1(i) ≠ f2(i).
Ваша задача — найти число различных планов эволюционирования таких, что если все покемоны во всех школах эволюционируют, количество покемонов каждого типа в каждой из школ останется таким же. Так как это число может быть большим, выведите остаток от его деления на 109 + 7.
В первой строке находятся два целых числа n и m (1 ≤ n ≤ 105, 1 ≤ m ≤ 106) — количество школ и количество типов покемонов.
Следующие n строк содержат описание покемонов в школах. i-я из этих строк начинается с целого числа gi (1 ≤ gi ≤ 105) — числа покемонов в i-й школе. После этого следуют gi целых чисел, означающие типа покемонов в i-й школе. Каждое из этих чисел находится в пределах от 1 до m.
Общее число покемонов (сумма чисел gi) не превышает 5·105.
Выведите остаток от деления числа удовлетворяющих уставу планов эволюционирования на 109 + 7.
2 3
2 1 2
2 2 3
1
1 3
3 1 2 3
6
2 4
2 1 2
3 2 3 4
2
2 2
3 2 2 1
2 1 2
1
3 7
2 1 2
2 3 4
3 5 6 7
24
В первом примере единственный корректный план эволюционирования выглядит так:
Во втором примере подходит любая перестановка чисел (1, 2, 3).
В третьем примере есть два корректных плана:
В четвертом примере единственный корректный план эволюционирования выглядит так:
