# CFR 757 C. Felicity is Coming! ( Hash )

Problem - C - Codeforces

TL: 2000 ms
ML: 256 MB

O( Sigma{ G } + M lg M )

この人怖い...

```const int MOD7 = ( int ) 1e9 + 7;

int N, M;
vvi G;

void init(){
cin >> N >> M;
G = vvi( N );
for( int i = 0; i < N; ++i ){
int sz; cin >> sz;
G[ i ] = vi( sz );
for( int j = 0; j < sz; ++j ){
cin >> G[ i ][ j ];
}
}
}

const int BASE = ( int ) 1e9 + 7;
const int MOD[] = { ( int ) 1e9 + 9, 15485863 };

vp trait;

void preprocess(){
trait = vp( M + 1 );
int base[] = { 1, 1 };
for( int i = 0; i < N; ++i ){
map< int, int > cnt;
for( int j = 0; j < G[ i ].size(); ++j ){
++cnt[ G[ i ][ j ] ];
}
for( auto it = cnt.begin(); it != cnt.end(); ++it ){
( trait[ it->first ].first += 1LL * it->second * base[ 0 ] % MOD[ 0 ] ) %= MOD[ 0 ];
( trait[ it->first ].second += 1LL * it->second * base[ 1 ] % MOD[ 1 ] ) %= MOD[ 1 ];
}
base[ 0 ] = 1LL * base[ 0 ] * BASE % MOD[ 0 ];
base[ 1 ] = 1LL * base[ 1 ] * BASE % MOD[ 1 ];
}
map< pii, set< int > > trait2pool;
for( int i = 1; i <= M; ++i ){
trait2pool[ trait[ i ] ].emplace( i );
}
vi fact( M + 1 );
fact[ 0 ] = 1;
for( int i = 1; i <= M; ++i ){
fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD7;
}
int ans = 1;
for( auto it = trait2pool.begin(); it != trait2pool.end(); ++it ){
ans = 1LL * fact[ it->second.size() ] * ans % MOD7;
}
cout << ans << endl;
}
```