bobo 得到一个二分图，包含 $n$ 个顶点（即没有奇环的图）。

他将每个顶点涂成黑色或白色，然后计算每条边的权值之积。一条边的权值由其两个端点的颜色决定。因此，对于给定的边，共有 $2 \times 2 = 4$ 种不同的权值。

现在 bobo 想知道所有 $2^n$ 种涂色方案下，权值乘积之和，结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含两个整数 $n, m$，分别表示顶点数和边数（$2 \le n \le 40$，$1 \le m \le 100$）。

为了方便起见，顶点编号为 $1, 2, \dots, n$。

接下来的 $m$ 行，每行包含 6 个整数 $a_i, b_i, v_{i,00}, v_{i,01}, v_{i,10}, v_{i,11}$，表示连接顶点 $a_i$ 和 $b_i$ 的一条边（$1 \le a_i, b_i \le n$，$0 \le v_{i,00}, v_{i,01}, v_{i,10}, v_{i,11} \le 10^9$）。

• 如果顶点 $a_i$ 和 $b_i$ 均为白色，则第 $i$ 条边的权值为 $v_{i,00}$。
• 如果顶点 $a_i$ 为白色且 $b_i$ 为黑色，则权值为 $v_{i,01}$。
• 如果顶点 $a_i$ 为黑色且 $b_i$ 为白色，则权值为 $v_{i,10}$。
• 如果顶点 $a_i$ 和 $b_i$ 均为黑色，则权值为 $v_{i,11}$。

输出格式

输出一个整数，表示总和。

样例

输入 1

2 1
1 2 1 2 3 4

输出 1

10

输入 2

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

输出 2

2