A person is playing a very magical game. In this game, there is a bipartite graph with $n$ vertices on each side, and the edges in the graph appear randomly according to certain rules.

To describe these rules, the person divides the edges into several groups. Each edge either does not belong to any group (in which case it will never appear) or belongs to exactly one group.

There are exactly three types of edge groups:

1. Each group contains exactly one edge, which appears with a probability of $50\%$.
2. Each group contains exactly two edges, which appear together with a probability of $50\%$ and do not appear together with a probability of $50\%$.
3. Each group contains exactly two edges, exactly one of which appears, each with a probability of $50\%$.

The appearance of edges in different groups is completely independent.

The person now knows the grouping of the edges and the type of each group, and wants to know the expected number of perfect matchings. Can you help her solve this problem?

Definition Explanation

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

For a bipartite graph with $n$ vertices on each side, a perfect matching is a set of $n$ edges that do not share any common vertices.

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

In the graph described in the problem, edges appear randomly, so the number of perfect matchings in this 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$, weighted by their probabilities: $$ \sum_{x \in V(X)}P[X=x]\cdot x $$ where $V(X)$ is the set of all possible values of $X$, and $P[X=x]$ is the probability that $X$ takes the value $x$.

Input

Read the data from standard input.

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

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

Output

Output to standard output.

Let $E$ be the expected number of perfect matchings. Output a single line representing: $$ (2^{n} E) \bmod (10^9 + 7) $$ It can be shown that the above expression is always an integer.

Examples

Input 1

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

Output 1

2

Input 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 2

7

Note 3

See ex_3.in and ex_3.ans in the download directory.

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 exist.

For another $5\%$ of the data, only $t = 0$ cases exist, and $m = n^2$, meaning the graph is a complete bipartite graph.

For another $20\%$ of the data, only $t = 0$ or $t = 1$ cases exist.

For another $20\%$ of the data, only $t = 0$ or $t = 2$ cases exist.

For $100\%$ of the data, $n \le 15$.