Description

After taking office, Yuuka’s first measure is to build Gensokyo’s highways. There are $n$ cities in Gensokyo, and initially there are no roads. Yuuka promised voters to cut taxes, so she plans to build only $n - 1$ roads to connect all these cities. There are exactly $n - 1$ construction companies, and each company wants to gain some benefits during road construction. Although these companies did not give Yuuka money before the election, she still intends to maintain good relations with them, since she is counting on them to help her build the wall. So she plans to have each construction company be responsible for exactly one road.

Each construction company has told Yuuka between which pairs of cities it is capable of building a road. Yuuka will choose $n - 1$ edges that can connect all cities in Gensokyo, then assign each edge to a construction company that can build it, with each company building exactly one edge.

Yuuka now wants to know how many possible schemes there are in total. Two schemes are different if and only if either the set of edges to be built is different, or the assignment of companies to edges is different.

Input Format

The first line contains an integer $n$, the number of cities.

Lines $2$ through $n$: line $i + 1$ describes the list of roads that the $i$-th construction company can build. It starts with a non-negative integer $m_i$, the number of roads it can build; then follow $m_i$ pairs of integers $u, v$, each pair denoting the endpoints of an edge. Within a company’s list, there are no duplicate edges and no self-loops.

Output Format

Output a single integer on one line: the number of all possible schemes modulo $10^9+7$.

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

17

Hint

Constraints

• For $20\%$ of the test points, $n \le 5$.
• For $50\%$ of the test points, $n \le 8$.
• For $60\%$ of the test points, $n \le 10$.
• For $100\%$ of the test points, $2 \leq n \le 17$, $0 \leq m_i \leq \frac{n(n - 1)}{2}$, $1 \leq u, v \leq n$.

Translated by ChatGPT 5