Background

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

Problem Description

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)$。

Input Format

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 Format

Output one line with one integer, representing the result modulo $(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

Hint

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$。

Translated by ChatGPT 5