{"raw_statement":[{"iden":"background","content":"译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T3。$\\texttt{0.5s,1G}$。"},{"iden":"statement","content":"给定有向图 $G=(V,E)$，其中 $|V|=N,|E|=M$，满足 $\\forall (u,v)\\in E$，都有 $u\\lt v$。\n\n定义边的一种**着色方案**为一种给每条边分配 $0/1$ 权值的方式。记 $(u,v)$ 边权为 $w(u,v)$。\n\n定义节点 $(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})$。\n\n定义一种着色方案是好的，当且仅当对于每一对 $(u,v)$，都有 $(u,v)$ 间的所有路径的权值模 $2$ 后的余数相等。\n\n求出好的着色方案数，对 $(10^9+7)$ 取模。"},{"iden":"input","content":"第一行，两个正整数，$N,M$，含义见题面。\n\n接下来 $M$ 行，每行两个正整数 $u,v$，表示 $(u,v)\\in E$。"},{"iden":"output","content":"输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。"},{"iden":"note","content":"\n#### 样例解释\n\n样例 $1$ 解释：显然只有 $1,4$ 间有两条路径 $(1,2,3,4),(1,4)$。\n\n当 $w(1,4)=0$ 时，$(1,2,3,4)$ 路径上只能取 $0$ 或 $2$ 条边边权为 $1$，方案数为 $4$；\n\n当 $w(1,4)=1$ 时，$(1,2,3,4)$ 路径上只能取 $1$ 或 $3$ 条边边权为 $1$，方案数为 $4$。\n\n所以答案为 $8$。\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证：\n\n- $1\\le N\\le 400$，$0\\le M\\le 400$；\n- $1\\le u\\lt v\\le n$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$  | $21$  | $N \\leq 6$   |\n| $2$  | $20$  | $N \\leq 13$  |\n| $3$  | $37$  | $N, M \\leq 50$ |\n| $4$  | $22$  | 无额外约束 |\n\n"}],"translated_statement":null,"sample_group":[["4 4\n1 2\n2 3\n3 4\n1 4","8"],["4 4\n1 3\n1 4\n2 3\n2 4","16"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}