现在给定一个包含 $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

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$ 种组合。