Problem E
Dim Sum

There are $n$ people (labelled $1, \dots , n$ counterclockwise) sitting around a round table, equally spaced. There are $n$ dishes (labelled $1, \dots , n$) on a rotating tray on the table. At the beginning, dish $i$ is right in front of person $i$ ($i=1, \dots ,n$). Person $i$ has an unordered set of dishes $S_ i$ (possibly empty) that he/she wants. At time $0$, the tray can start rotating either clockwise or counterclockwise at a speed $1/n$ revolution per second (i.e., one position per second). The direction of rotation cannot change once the tray is in motion. At any time, if there is a dish right in front of a person that he/she wants, he/she can get his/her portion instantaneously (assume there is sufficient number of portions in each dish to satisfy everyone). We choose the direction of rotation that minimizes the time needed for everyone to get all the food they want.

For example, in the above figure, $S_1 = \{ \} , S_2 = \{ 1\} , S_3 = \{ 1,3\} $. If we rotate clockwise, then Person $2$ will get Dish $1$ at time $2$, Person $3$ gets Dish $3$ at time $0$, and will get Dish $1$ at time $1$, and hence the time needed is $2$. One can check that the time needed for counterclockwise is also $2$. Therefore the minimum time is $2$.

The list of sets of dishes for each person $(S_1,S_2, \dots ,S_ n)$ is called a food assignment. In this problem, we not only consider one food assignment, but all food assignment that satisfies certain constraints. Assume person $i$ can only have dishes in the set $T_ i$ due to dietary constraints (so $S_ i$ must be a subset of $T_ i$). The task is to find the sum of the minimum time needed over all possible food assignment $(S_1,S_2, \dots ,S_ n)$ satisfying the dietary constraints, modulo $1\, 000\, 000\, 009$.

As an example, consider the first sample input. We have $T_1 = \{ \} , T_2 = \{ 1\} , T_3 = \{ 1,3\} $, so $S_1 = \{ \} $. There are 8 possible food assignments:

The sum of the minimum time needed is $8$.

Input

The first line contains the integer $n$ ($1 \leq n \leq 500\, 000$). Each of the next $n$ lines describes a set $T_ i$ ($i=1, \dots ,n$). The first integer in each line is $|T_ i|$ (the size of $T_ i$), followed by $|T_ i|$ integers which are the elements of $T_ i$. It is guaranteed that $|T_1| + \dots |T_ n| \leq 500\, 000$.

Output

Output the sum of the minimum time needed over all possible food assignment satisfying the dietary constraints, modulo $1\, 000\, 000\, 009$.

3
0
1 1
2 1 3

8

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

14676