Background

After a long period of hard work, ${\rm TimeTraveller\ }$ finally got into his dream school.

Problem Description

As a foodie, ${\rm \ TimeTraveller}$ did not go to register on his first day after enrollment. Instead, he went to the cafeteria to check the dishes. However, for various reasons, there are very few dishes in the cafeteria this semester, and the cafeteria has made a menu for several days. Therefore, during this semester, the dishes provided each day in the future will cycle in turn according to the menu.

After hearing this, ${\rm TimeTraveller\ }$ was of course devastated, but he still hopes that what he eats every day will not be too repetitive. So ${\rm \ TimeTraveller\ }$ decides that it is enough as long as the dishes he eats do not overlap with the previous day. But as a foodie, ${\rm \ TimeTraveller\ }$ also does not want to go hungry, so he must eat at least one dish every day.

${\rm TimeTraveller\ }$ wants to know how many legal planning schemes he has, but he finds there are simply too many. So he asks you for help and hopes you can write a program to compute it for him.

Input Format

The first line contains three positive integers $n,m,k$, meaning this semester has $n$ days, there are $m$ kinds of dishes in total, and the school has made a $k$-day menu (all dishes are numbered from $1$ to $m$, and it is guaranteed that $n \ge k$).

The next $k$ lines describe the menu. In each line, the first number is $p$, meaning the school prepared $p$ dishes on that day, followed by $p$ numbers indicating which dishes they are (it is guaranteed that $p$ does not exceed $m$, and these $p$ numbers are all distinct).

Output Format

Output the number of legal schemes. Since the answer may be too large, you only need to output the value modulo $1e9+7$.

3 3 2
2 1 3
2 2 3

11

10 7 3
5 1 2 3 4 5
3 1 3 7
4 1 2 6 7

730285459

Hint

Sample $1$ Explanation:

Scheme $1$: On day $1$, eat dishes $1,3$; on day $2$, eat dish $2$; on day $3$, eat dishes $1,3$.

Scheme $2$: On day $1$, eat dishes $1,3$; on day $2$, eat dish $2$; on day $3$, eat dish $3$.

Scheme $3$: On day $1$, eat dishes $1,3$; on day $2$, eat dish $2$; on day $3$, eat dish $1$.

Scheme $4$: On day $1$, eat dish $3$; on day $2$, eat dish $2$; on day $3$, eat dishes $1,3$.

Scheme $5$: On day $1$, eat dish $3$; on day $2$, eat dish $2$; on day $3$, eat dish $3$.

Scheme $6$: On day $1$, eat dish $3$; on day $2$, eat dish $2$; on day $3$, eat dish $1$.

Scheme $7$: On day $1$, eat dish $1$; on day $2$, eat dishes $2,3$; on day $3$, eat dish $1$.

Scheme $8$: On day $1$, eat dish $1$; on day $2$, eat dish $3$; on day $3$, eat dish $1$.

Scheme $9$: On day $1$, eat dish $1$; on day $2$, eat dish $2$; on day $3$, eat dishes $1,3$.

Scheme $10$: On day $1$, eat dish $1$; on day $2$, eat dish $2$; on day $3$, eat dish $3$.

Scheme $11$: On day $1$, eat dish $1$; on day $2$, eat dish $2$; on day $3$, eat dish $1$.

Constraints:

• For $20\%$ of the testdata, $n \le 5, m \le 7, k \le 5$.

• For $45\%$ of the testdata, $n \le 50000, m \le 7, k \le 7$.

• For another $10\%$ of the testdata, $n \le 10^7, m \le 2, k = 1$.

• For $70\%$ of the testdata, $n \le 10^7, m \le 7, k \le 7$.

• For $100\%$ of the testdata, $n \le 10^7, m \le 7, k \le 300$.

Translated by ChatGPT 5