题目描述

有一个包含 $N$ 个顶点、$M$ 条边的有向图 $G$。顶点编号为 $1$ 到 $N$。边的编号为 $1$ 到 $M$。边 $i$ 从顶点 $x_i$ 指向顶点 $y_i$。此外，所有的边都满足 $x_i<y_i$，且不存在重边。

现在可以从 $G$ 的 $M$ 条边中选择任意一个子集，并从图 $G$ 中删去这些边，得到一个新的图 $G'$。总共有 $2^M$ 种不同的 $G'$。

在每一个 $G'$ 上，高桥君和青木君玩如下的游戏。首先，在顶点 $1$ 和 $2$ 各放一个棋子。高桥君先手，然后两人轮流进行如下操作：

• 选择某一个棋子所在的顶点 $x_i$ 出发的某条边 $i$，将该棋子从 $x_i$ 移动到 $y_i$（如果有两个棋子在 $x_i$，则只能移动其中一个）。允许两个棋子停在同一个顶点。

无法进行操作的一方判负。两人都采取最优策略。

在 $2^M$ 种 $G'$ 中，使高桥君获胜的 $G'$ 有多少种？请输出这个数量对 $10^9+7$ 取模的结果。

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $\dots$ $x_M$ $y_M$

输出格式

输出使高桥君获胜的 $G'$ 的数量。结果需要对 $10^9+7$ 取模。

样例 1

输入

2 1
1 2

输出

1

样例 2

输入

3 3
1 2
1 3
2 3

输出

6

样例 3

输入

4 2
1 3
2 4

输出

2

样例 4

输入

5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4

输出

816

说明/提示

约束

• $2 \leq N \leq 15$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq x_i, y_i \leq N$
• 所有的 $(x_i, y_i)$ 互不相同。

样例解释 1

$G'$ 有如下 $2$ 种可能。高桥君获胜用 ○ ，青木君获胜用 × 表示。

样例解释 2

$G'$ 有如下 $8$ 种可能。

由 ChatGPT 5 翻译