P10682 [COTS 2024] Odd-Even Pumpkin Tikvani

Translated from [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T3。$\texttt{0.5s,1G}$。

Given a directed graph $G=(V,E)$, where $|V|=N,|E|=M$, it satisfies that for all $(u,v)\in E$, we have $u\lt v$。 Define an **edge coloring scheme** as a way to assign a $0/1$ weight to each edge. Let the weight of edge $(u,v)$ be $w(u,v)$。 Define a path from node $u$ to node $v$ as a sequence $(a_1,a_2,\cdots,a_k)$ such that $a_1=u,a_k=v$, and for all $1\le i\lt k$, we have $(a_i,a_{i+1})\in E$。Define the weight of a path as the sum of the weights of all edges on it, i.e., $\displaystyle \sum_{i=1}^{k-1} w(a_{i},a_{i+1})$。 A coloring scheme is called good if and only if for every pair $(u,v)$, the remainders modulo $2$ of the weights of all paths between $(u,v)$ are the same. Compute the number of good coloring schemes, modulo $(10^9+7)$。

The first line contains two positive integers $N,M$, with meanings as described above。 The next $M$ lines each contain two positive integers $u,v$, indicating $(u,v)\in E$。

Output one line with one integer, representing the result modulo $(10^9+7)$。

#### Sample Explanation Explanation for sample $1$: Obviously, only between $1$ and $4$ are there two paths $(1,2,3,4),(1,4)$。 When $w(1,4)=0$, on the path $(1,2,3,4)$ you can only choose $0$ or $2$ edges whose weights are $1$, so the number of schemes is $4$； When $w(1,4)=1$, on the path $(1,2,3,4)$ you can only choose $1$ or $3$ edges whose weights are $1$, so the number of schemes is $4$。 Therefore, the answer is $8$。 #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1\le N\le 400$，$0\le M\le 400$； - $1\le u\lt v\le n$。 | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $21$ | $N \leq 6$ | | $2$ | $20$ | $N \leq 13$ | | $3$ | $37$ | $N, M \leq 50$ | | $4$ | $22$ | No additional constraints | Translated by ChatGPT 5