从标准输入读入数据。

第一行两个数 $n$ 和 $m$，表示图左右点数的数量和边的组的个数。我们用 $(a,b)$ （其中 $1\le a,b\le n$）表示一条左端点为二分图左侧第 $a$ 个点，右端点为二分图右侧第 $b$ 个点的边。

接下来 $m$ 行，每行描述一个组。开头第一个数 $t$ 表示组的种类，$t=0$ 表示是一条边的组，$t=1$ 表示是两条边的组中的第一种，$t=2$ 表示是两条边的组中的第二种。如果 $t=0$， 接下来两个数 a1,b1a_1,b_1a​1​​,b​1​​ 表示组内的第一条边；否则，接下来四个数 a1,b1,a2,b2a_1,b_1,a_2,b_2a​1​​,b​1​​,a​2​​,b​2​​， 表示该组内的两条边分别为 (a1,b1)(a_1,b_1)(a​1​​,b​1​​) 和 (a2,b2)(a_2,b_2)(a​2​​,b​2​​)。保证每条边至多出现一次。

输出到标准输出。

假设期望的完美匹配数量是$E$。输出一行表示

$$\left(2^{n}E\right)mod({10}^9+7)$$

可以看出上式一定是一个整数。

样例输入1

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

样例输出1

2

样例输入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

样例输出2

7

对于 $5\%$ 的数据 $n\le 5$ 。

对于另 $5\%$ 的数据 $n\le 8$ 。

对于另 $10\%$ 的数据 $n\le 10$ 。

对于另 $15\%$ 的数据，只有$t=0$ 的情况。

对于另 $5\%$ 的数据，只有$t=0$ 的情况，且m=n2m = n^2m=n​2​​，也就是该图为一个完全图。

对于另 $20\%$ 的数据，只有 $t=0$ 或者 $t=1$ 的情况。

对于另 $20\%$ 的数据，只有 $t=0$ 或者 $t=2$ 的情况。

对于 $100\%$ 的数据，$n\le 15$。