题目背景

译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T3。$\texttt{0.5s,1G}$。

题目描述

给定有向图 $G=(V,E)$，其中 $|V|=N,|E|=M$，满足 $\forall (u,v)\in E$，都有 $u\lt v$。

定义边的一种着色方案为一种给每条边分配 $0/1$ 权值的方式。记 $(u,v)$ 边权为 $w(u,v)$。

定义节点 $(u,v)$ 的路径为一个序列 $(a_1,a_2,\cdots,a_k)$，满足 $a_1=u,a_k=v$，且 $\forall 1\le i\lt k$，都有 $(a_i,a_{i+1})\in E$。定义路径的权值为其上所有边的权值之和，即 $\displaystyle \sum_{i=1}^{k-1} w(a_{i},a_{i+1})$。

定义一种着色方案是好的，当且仅当对于每一对 $(u,v)$，都有 $(u,v)$ 间的所有路径的权值模 $2$ 后的余数相等。

求出好的着色方案数，对 $(10^9+7)$ 取模。

输入格式

第一行，两个正整数，$N,M$，含义见题面。

接下来 $M$ 行，每行两个正整数 $u,v$，表示 $(u,v)\in E$。

输出格式

输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

4 4
1 2
2 3
3 4
1 4

8

4 4
1 3
1 4
2 3
2 4

16

提示

样例解释

样例 $1$ 解释：显然只有 $1,4$ 间有两条路径 $(1,2,3,4),(1,4)$。

当 $w(1,4)=0$ 时，$(1,2,3,4)$ 路径上只能取 $0$ 或 $2$ 条边边权为 $1$，方案数为 $4$；

当 $w(1,4)=1$ 时，$(1,2,3,4)$ 路径上只能取 $1$ 或 $3$ 条边边权为 $1$，方案数为 $4$。

所以答案为 $8$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le N\le 400$，$0\le M\le 400$；
• $1\le u\lt v\le n$。