题目描述

有一个有 $N$ 个顶点和 $M$ 条边的有向图 $G$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边是从 $x_i$ 指向 $y_i$ 的。这里，满足 $x_i < y_i$。并且 $G$ 中没有重复的边。

考虑在 $G$ 中选择一组边的子集，并从 $G$ 中删除这些边，得到另一个图 $G'$。总共有 $2^M$ 种不同的 $G'$。

Alice 和 Bob 在以下游戏中对抗。游戏在 $G'$ 上进行。首先，在顶点 $1$ 和 $2$ 上放置两个棋子，一个棋子在每个顶点上。然后，从 Alice 开始，Alice 和 Bob 交替执行以下操作：

• 选择一条边 $i$，使得顶点 $x_i$ 上有放置了棋子，并将棋子移动到顶点 $y_i$ 上（如果顶点 $x_i$ 上有两个棋子，则只移动一个）。两个棋子可以放在同一个顶点上。

当某个玩家无法执行操作时，该玩家输掉游戏。我们假设两个玩家都会以最佳策略进行游戏。

在 $2^M$ 种不同的 $G'$ 中，有多少种会导致 Alice 获胜的情况？将计数结果对 $10^9+7$ 取模。

约束条件

• $2 ≤ N ≤ 15$
• $1 ≤ M ≤ N(N-1)/2$
• $1 ≤ x_i < y_i ≤ N$
• 所有 $(x_i,\\ y_i)$ 都是不同的。

输入

输入从标准输入读取，格式如下：

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出

打印导致 Alice 获胜的 $G'$ 的数量，对 $10^9+7$ 取模。

示例输入 1

2 1
1 2

示例输出 1

1

下图显示了两种可能的 $G'$。一个被标记为 ○ 的图导致 Alice 获胜，一个被标记为 × 的图导致 Bob 获胜。

示例输入 2

3 3
1 2
1 3
2 3

示例输出 2

6

下图显示了八种可能的 $G'$。

示例输入 3

4 2
1 3
2 4

示例输出 3

2

示例输入 4

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

示例输出 4

816