The quadrennial Gensokyo general election has begun. Recently, the biggest issue in Gensokyo is the influx of mysterious youkai, which has disrupted the former order of the land. However, the establishment youkai (and humans) such as Reimu Hakurei and Yukari Yakumo spend their days talking about equality for all youkai and the diversification of Gensokyo, yet they fail to provide reasonable solutions to the various major problems currently facing the land.

Yuuka Kazami is one of the few powerful youkai in Gensokyo who has realized the severity of the situation. She bravely stepped forward to participate in the general election, proposing a series of plans including building a wall on the border of Gensokyo (and making the humans pay for it) and vigorously developing infrastructure to reduce unemployment. She became the unexpected dark horse of the election year and was successfully elected as the President of Gensokyo.

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

Each construction company has told Yuuka which cities they are capable of connecting. Yuuka intends to select $n - 1$ edges that can connect all the cities in Gensokyo, assign each edge to a construction company capable of building it, and ensure that each construction company is responsible for exactly one edge.

Yuuka now wants to know how many possible schemes there are. Two schemes are different if and only if they have a different set of edges or a different assignment of edges to companies.

Input

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

The next $n - 1$ lines each describe the roads that the $i$-th construction company can build: it starts with a non-negative integer $m_i$, representing the number of roads it can build; this is followed by $m_i$ pairs of integers, where each pair represents the two endpoints of an edge. There will be no duplicate edges, and no self-loops.

Output

Output a single integer representing the number of possible schemes modulo $10^9 + 7$.

Examples

Input 1

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

Output 1

17

Subtasks