FireGhost and friends are planning to travel to VNOI city!

There are ~n~ famous landscapes in the city. As for planning, the friends need to decide the list of the landscapes that they are going to visit. Therefore there are ~2^n~ different travel plans, from not visiting any landscapes at all, to visiting all of the landscapes.

However, not every plan will make FireGhost's friends happy. He has ~m~ friends. Each of the friends has a wishlist, and each entry in the list will either be "I want to visit the ~p~-th place" or "I don't want to visit the ~p~-th place". Fortunately, everyone is easy-going: a friend will be happy if the plan satisfies at least one entry in their wishlist.

FireGhost is curious about the number of plans that make all of his friends happy. Can you help him?

Input

The first line contains two integers ~n~ and ~m~ (~1 \le n \le 10^5~, ~1 \le m \le 20~) — the number of landscapes and the number of friends, respectively.

The ~i~-th of the next ~m~ lines starts with an integer ~k~ (~1 \leq k \leq n~) — the number of entries in the wishlist of the ~i~-th friend, followed by ~k~ integers ~a_1, a_2, \ldots, a_k~ (~1 \le |a_j| \le n~)  — the entries' description:

• if ~a_j > 0~, the ~i~-th friend wishes to visit the ~a_j~-th landscape,

• otherwise, if ~a_j < 0~, the ~i~-th friend wishes not to visit the ~|a_j|~-th landscape.

It is guaranteed that ~|a_{u}| \neq |a_{v}|~ for all ~1 \le u < v \le k~.

Output

Output the number of plans that make all of FireGhost's friends happy, modulo ~10^9 + 7~.

Scoring

• Subtask 1 (~30~ points): ~n \leq 20~ and ~m \leq 5~

• Subtask 2 (~94~ points): ~n \leq 10^3~ and ~m \leq 15~

• Subtask 3 (~180~ points): No additional constraints.

The total score for this problem is ~304~.

Sample Input 1

4 2
2 1 -4
1 3

Sample Output 1

6

Sample Input 2

7 1
2 -2 6

Sample Output 2

96

Sample Input 3

6 3
3 1 4 -2
2 2 3
3 -5 2 -6

Sample Output 3

36

Notes

In the first test case, only these plans (the landscapes lists) can make all of the friends happy:

1. ~\{3\}~,

2. ~\{1, 3\}~,

3. ~\{2, 3\}~,

4. ~\{1, 2, 3\}~,

5. ~\{1, 3, 4\}~,

6. ~\{1, 2, 3, 4\}~.

The other plans will make somebody unhappy. For example:

• The plan ~\{3, 4\}~ will not make the first friend happy, because he does not want to visit the ~4~-th landscape.

• The plan ~\{1\}~ will not make the second friend happy, because he the only place he wants to visit is the ~3~-rd landscape.

• The plan ~\{4\}~ will make nobody happy.