现在给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1$ 到 $N$，且对于每一条有向边 $(u, v)$，满足 $u < v$。边的染色是指为每一条边分配一个值 $0$ 或 $1$。我们将边 $(u, v)$ 的值记为 $w(u, v)$。
顶点 $u$ 和 $v$ 之间的一条路径是顶点序列 $(a_1, \dots, a_k)$，满足 $a_1 = u$ 且 $a_k = v$。此外，对于 $1$ 到 $k-1$ 之间的每一个 $i$，都存在一条边 $(a_i, a_{i+1})$。路径的权重是其所有边权重的总和，即 $w(a_1, a_2) + \dots + w(a_{k-1}, a_k)$。
如果对于每一对顶点 $(u, v)$ 以及它们之间的任意两条路径，这两条路径的权重模 $2$ 的余数相同，则称该染色 $w$ 为“好的”。
由于好的染色的数量可能很大，请输出其对 $10^9 + 7$ 取模后的结果。
输入格式
第一行包含自然数 $N$ 和 $M$。
接下来的 $M$ 行包含不同的数对 $u$ 和 $v$ ($1 \le u < v \le N$)，表示图中的边。
输出格式
在唯一的一行中输出好的染色的数量对 $10^9 + 7$ 取模后的结果。
子任务
在所有子任务中，满足 $1 \le N \le 400$，$0 \le M \le 400$。
| 子任务 | 分值 | 约束 |
|---|---|---|
| 1 | 21 | $N \le 6$ |
| 2 | 20 | $N \le 13$ |
| 3 | 37 | $N, M \le 50$ |
| 4 | 22 | 无额外约束 |
样例
输入 1
4 4 1 2 2 3 3 4 1 4
输出 1
8
输入 2
4 4 1 3 1 4 2 3 2 4
输出 2
16
说明
对于第一个样例的解释：
路径 $1 \to 2 \to 3 \to 4$ 和 $1 \to 4$ 的权重模 $2$ 必须相等。如果给边 $(1, 4)$ 分配权重 $0$，则剩余边中必须有偶数条边的权重为 $1$，这会产生 $4$ 种组合。如果给边 $(1, 4)$ 分配权重 $1$，则剩余边中必须有奇数条边的权重为 $1$，这也产生 $4$ 种组合。