P10682 [COTS 2024] 奇偶南瓜 Tikvani

译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) 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)$ 取模。

无

无

#### 样例解释 样例 $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$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $21$ | $N \leq 6$ | | $2$ | $20$ | $N \leq 13$ | | $3$ | $37$ | $N, M \leq 50$ | | $4$ | $22$ | 无额外约束 |