Problem Description

Someone is playing a very intriguing game. In this game, there is a bipartite graph with $n$ vertices on each side, and the edges appear according to certain rules.

To describe these rules, the edges are grouped into several categories. Each edge either does not belong to any group (such edges will never appear) or belongs to exactly one group.

There are exactly three types of edge groups:

1. Each group of this type contains only one edge, which has a $50\%$ chance of appearing.
2. Each group of this type contains exactly two edges, which have a $50\%$ chance of appearing together and a $50\%$ chance of not appearing together.
3. Each group of this type contains exactly two edges, and exactly one of them appears, each with a $50\%$ chance.

The appearance of edges in different groups is completely independent.

Given the grouping of the edges and the types of groups, the person wants to know the expected number of perfect matches. Can you help her solve this problem?

Input Format

Input is read from the standard input.

The first line contains two numbers $n$ and $m$, representing the number of vertices on each side of the bipartite graph and the number of edge groups, respectively. We use $(a, b)$ (where $1 \le a, b \le n$) to denote an edge with the left endpoint being the $a$-th vertex on the left side and the right endpoint being the $b$-th vertex on the right side.

The next $m$ lines describe each group. The first number $t$ indicates the type of the group: $t=0$ means it is a single-edge group, $t=1$ means it is the first type of two-edge group, and $t=2$ means it is the second type of two-edge group. If $t=0$, the next two numbers $a_1, b_1$ denote the single edge in the group; otherwise, the next four numbers $a_1, b_1, a_2, b_2$ denote the two edges $(a_1, b_1)$ and $(a_2, b_2)$ in the group. It is guaranteed that each edge appears at most once.

Output Format

Output is written to the standard output.

Let $E$ be the expected number of perfect matches. Output one line representing
$$ (2^n E) \bmod (10^9 + 7) $$
It can be seen that the above expression is always an integer.

Sample Input and Output

Input Sample #1

2 2
1 2 1 2 2
2 1 2 1 1

Output Sample #1

2

Input Sample #2

3 5
1 1 2 3 3
1 3 2 2 2
1 1 1 1 3
1 2 1 3 1
0 2 3

Output Sample #2

7

Input Sample #3

4 9
2 4 1 4 2
1 3 2 1 4
2 2 1 4 4
2 3 4 1 1
2 4 3 2 4
2 2 2 3 1
0 1 3
0 3 3
1 2 3 1 2

Output Sample #3

20

Notes/Hints

Definition Explanation

If you are familiar with the definitions of perfect matchings and expectations, you can skip this section.

For a bipartite graph with $n$ vertices on each side, a perfect matching is a set of $n$ edges with no common vertices.

Two perfect matchings are considered different if and only if they contain at least one different edge. The number of perfect matchings in a bipartite graph is defined as the number of distinct perfect matchings that can be found in the graph.

In the context of this problem, the edges appear randomly, so the number of perfect matchings in the graph is a random variable. The expectation of a (discrete) random variable $X$ is defined as the weighted average of all possible values of $X$ with probabilities as weights, i.e.,
$$ \sum_{x \in V(X)} P[X=x] \cdot x $$
where $V(X)$ denotes the set of all possible values of $X$, and $P[X=x]$ denotes the probability that $X$ takes the value $x$.

Data Size and Constraints

For $5\%$ of the data, $n \le 5$.
For another $5\%$ of the data, $n \le 8$.
For another $10\%$ of the data, $n \le 10$.
For another $15\%$ of the data, only $t = 0$ cases are present.
For another $5\%$ of the data, only $t = 0$ cases are present, and $m = n^2$, meaning the graph is a complete graph.
For another $20\%$ of the data, only $t = 0$ or $t = 1$ cases are present.
For another $20\%$ of the data, only $t = 0$ or $t = 2$ cases are present.
For $100\%$ of the data, $n \le 15$.

见题面 Input 部分

见题面 Output 部分