In Canada, the Confusing Codeforces Contest (CCC) is a very popular programming contest amongst high school students. The competition is done on-site in the prestigious "York University" in Toronto. Unfortunately for the contestants, the contest sign-up process is extremely confusing, rivaling that of Topcoder. Still, Alex is determined to win the competition by any means necessary.

Alex starts out by asking the front desk clerk (person #1), but they are typically clueless and isn't exactly sure how to either. They do, however, know how to direct Alex to another person. The person Alex will be directed to will always be smarter than they are, but that person might not know the answer either. In fact, of the $N$ contest organizers, only one person (person #N) knows the answer. Everyone except person #N will try to redirect Alex to someone else smarter than them. The person with a larger number is always smarter.

The process would be pretty straightforward if everybody would keep redirecting Alex until he reached the last person, who has the answer. Unfortunately not all the organizers get along well. In fact, many of them hold grudges against each other after the fight over the great LowerBound Systests of 2017. Specifically, there are $K$ groups of people where each member holds a grudge against every other member of the group. If two people hold a grudge against each other, they will not direct Alex to the other person.

After being redirected numerous times, Alex was starting to get angry, and wanted to find out how many possible paths there are to finding the answer.

If a contest organizer doesn't have anyone to direct Alex to, Alex will rage quit and go do web dev instead. Obviously, we don't want that to happen, so help him find the answer!

Input Specification

The first line will contain $N$ $(1\le N\le {10}^6)$, the number of contest organizers.

The second line will contain $K$ $(0\le K\le 14)$, the number of groups of people who hold grudges.

The next $K$ lines will begin with $X$ $(0\le X\le N)$, the number of people in the group, then followed by $X$ integers; describing the people in the group.

Output Specification

Output a single integer, the number of ways to get to the end, modulo ${10}^9+7$.

Constraints

Subtask 1 [10%]

$N\le 9$

Subtask 2 [20%]

$N\le 1000$

Subtask 3 [20%]

$\sum \left(X^2\right)\le 1000000$

Subtask 4 [20%]

$K\le 7$

Subtask 5 [30%]

No additional constraints.

Sample Input 1

3
2
2 1 2
2 2 3

Sample Output 1

1

Sample Explanation 1

Person #1 and person #2 don't like each other very much, so person #1 can only refer Alex to person #3. This is the only way Alex can get to the last person. Note that because #1 and #3 are not in the same group, they will not hold a grudge against each other, even if they share a group with #2.

Sample Input 2

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

Sample Output 2

0

Sample Explanation 2

None of the organizers like each other, so they won't refer Alex to anyone else. This is a sign of bad leadership/management in the contest. Unfortunately, Alex won't be able to get to the last person and register for the CCC.

Sample Input 3

5
3
2 1 3
2 2 4
2 3 5

Sample Output 3

4

Sample Explanation 3

The possible paths are:

$1\to 2\to 3\to 4\to 5$

$1\to 2\to 5$

$1\to 4\to 5$

$1\to 5$