Criptomonede

Gomory and Hu have started investing in cryptocurrencies. On their investment plan there are $n$ of the most popular cryptocurrencies known to them.

Every day, Gomory, being very passionate about investments, wants to invest $1$ GH in several cryptocurrencies. Since Hu is his much more careful and responsible friend, he allows Gomory to choose only a subset of these investments.

At the end of their investment plan, which lasts $k$ days, the two calculate their profit. Since they are very smart, they figured out how the cryptocurrency market works and how they can compute their profit. Thus, they realized that the final profit is the product of the GH units invested in each cryptocurrency.

Because they have such an exciting life, they will try all possible ways of investing, and at the very end they will count the money obtained from the entire process. The two ask for your help and ask you to compute how rich they will be.

Task

Formally, you are given $n$ and $k$ sequences of the form: $m_i$, $p_i$, $a_{i, 1}$, $a_{i, 2}$, $\ldots$, $a_{i, m_i}$ $(1 \le i \le k)$.

Starting from a zero array of length $n$, for each $i$, a subsequence $S_i$ of exact size $p_i$ is chosen from the array $a_i$, and the elements at the positions in $S_i$ are incremented by $1$ in the array of length $n$. After performing the $k$ operations, the product of the elements of the array is computed.

You are asked to output the sum of the products of the elements of the array modulo $10^9 + 7$, over all possible ways of choosing the subsequences during the $k$ operations.

Input Data

On the first line, the numbers $n$ and $k$ are read, in this order, with the meaning from the statement.

On the next $k$ lines, the parameters for the $k$ days are given, in the following order: $m_i$, $p_i$, $a_{i, 1}$, $a_{i, 2}$, $\ldots$, $a_{i, m_i}$.

Output Data

You must output a single number representing the sum of the products of the elements of the final array modulo $10^9+7$, considering all possible ways of choosing the subsequences during the $k$ operations.

Constraints

• $1 \le n \le 14$
• $1 \le k \le 20$
• $1 \le p_i \le m_i \le n$
• $1 \le a_{i, 1} < a_{i, 2} < \ldots < a_{i, m_i} \le n$

Example

stdin

3 2
3 2 1 2 3
2 2 2 3

stdout

4

Explanation

In the given example, there are three possible final configurations:

1. We choose on the first day $(1 , 2)$, and on the second day $(2, 3)$. The final array will be $[1,2,1]$, and the product of the elements is $2$.
2. We choose on the first day $(1 , 3)$, and on the second day $(2, 3)$. The final array will be $[1,1,2]$, and the product of the elements is $2$.
3. We choose on the first day $(2 , 3)$, and on the second day $(2, 3)$. The final array will be $[0,2,2]$, and the product of the elements is $0$.

Thus, the answer is $2 + 2 + 0 = 4$.