ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4413: Felicity is Coming!

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4 通过：3
提交提交记录统计Web Board

题目描述

C. Felicity is Coming!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
It's that time of the year, Felicity is around the corner and you can see people celebrating all around the Himalayan region. The Himalayan region has n gyms. The i-th gym has gi Pokemon in it. There are m distinct Pokemon types in the Himalayan region numbered from 1 to m. There is a special evolution camp set up in the fest which claims to evolve any Pokemon. The type of a Pokemon could change after evolving, subject to the constraint that if two Pokemon have the same type before evolving, they will have the same type after evolving. Also, if two Pokemon have different types before evolving, they will have different types after evolving. It is also possible that a Pokemon has the same type before and after evolving.
Formally, an evolution plan is a permutation f of {1,2,...,m}, such that f(x)=y means that a Pokemon of type x evolves into a Pokemon of type y.
The gym leaders are intrigued by the special evolution camp and all of them plan to evolve their Pokemons. The protocol of the mountain states that in each gym, for every type of Pokemon, the number of Pokemon of that type before evolving any Pokemon should be equal the number of Pokemon of that type after evolving all the Pokemons according to the evolution plan. They now want to find out how many distinct evolution plans exist which satisfy the protocol.
Two evolution plans f1 and f2 are distinct, if they have at least one Pokemon type evolving into a different Pokemon type in the two plans, i. e. there exists an i such that f1(i)≠f2(i).
Your task is to find how many distinct evolution plans are possible such that if all Pokemon in all the gyms are evolved, the number of Pokemon of each type in each of the gyms remains the same. As the answer can be large, output it modulo 109+7.
Input
The first line contains two integers n and m (1≤n≤105, 1≤m≤106)− the number of gyms and the number of Pokemon types.
The next n lines contain the description of Pokemons in the gyms. The i-th of these lines begins with the integer gi (1≤gi≤105)− the number of Pokemon in the i-th gym. After that gi integers follow, denoting types of the Pokemons in the i-th gym. Each of these integers is between 1 and m.
The total number of Pokemons (the sum of all gi) does not exceed 5·105.
Output
Output the number of valid evolution plans modulo 109+7.
Examples
Input 
2 3
2 1 2
2 2 3
Output 
1
Input 
1 3
3 1 2 3
Output 
6
Input 
2 4
2 1 2
3 2 3 4
Output 
2
Input 
2 2
3 2 2 1
2 1 2
Output 
1
Input 
3 7
2 1 2
2 3 4
3 5 6 7
Output 
24
Note
In the first case, the only possible evolution plan is:
In the second case, any permutation of (1,2,3) is valid.
In the third case, there are two possible plans:
In the fourth case, the only possible evolution plan is:
每年的这个时候，费利西蒂就在附近，你可以看到喜马拉雅地区的人们在庆祝。喜马拉雅地区有n个健身房。第i个健身房里有gi只口袋妖怪。喜马拉雅地区有m种不同的口袋妖怪，数量从1到m不等。在这个节日里设立了一个特别的进化营，声称可以进化任何一种口袋妖怪。口袋妖怪的类型在进化后可能会发生变化，但前提是如果两个口袋妖怪在进化前具有相同的类型，则它们在进化后将具有相同类型。此外，如果两个口袋妖怪在进化前具有不同的类型，那么它们在进化后将具有不同的种类。口袋妖怪在进化前后也可能有相同的类型。

形式上，进化计划是{1,2，…，m}的置换f，使得f（x）=y意味着x型口袋妖怪进化为y型口袋妖怪。

健身房的领导者们对这个特殊的进化营很感兴趣，他们都计划进化自己的口袋妖怪。山上的协议规定，在每个健身房，对于每种类型的口袋妖怪，在进化任何口袋妖怪之前，该类型口袋妖怪的数量应等于根据进化计划进化所有口袋妖怪之后该类型口袋精灵的数量。他们现在想知道有多少不同的进化计划符合协议。

两个进化计划f1和f2是不同的，如果它们在两个计划中至少有一个口袋妖怪类型进化为不同的口袋妖怪类型，即存在一个i，使得f1（i）≠f2（i）。

你的任务是找出有多少不同的进化计划是可能的，这样，如果所有健身房中的所有口袋妖怪都进化了，那么每个健身房中每种类型的口袋妖怪的数量都保持不变。因为答案可能很大，所以将其模输出109+7。

输入格式

第一行包含两个整数n和m（1≤n≤105，1≤m≤106）−健身房数量和口袋妖怪类型数量。

接下来的n行包含对健身房中的Pokemons的描述。这些行中的第i行以整数gi（1≤gi≤105）开始，即第i个健身房中的口袋妖怪数量。之后是gi整数，表示第i个健身房的扑克类型。这些整数中的每一个都在1和m之间。

Pokemons的总数（所有gi的总和）不超过5105。

输出格式

输出模109+7的有效进化计划的数量。

输入样例 复制 

2 3
2 1 2
2 2 3

输出样例 复制 

1

分类标签