分数: 1600 点
问题陈述
有一个有向图 G 与 N 顶点和 M 边缘。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 i 定向自 x_i to y_i。 在这里, x_i < y_i 成立。 此外,不存在重边 G.
考虑选择该集合的子集 M 边缘 G,并从 G 获取另一张图 G'。 有 2^M 不同可能的图表为 G'.
Alice 和 Bob 在以下游戏中对战 G'。 首先,将两块放在顶点上 1 和 2,每人一个。 然后,从Alice开始,Alice和Bob交替执行以下操作:
- 选择一条边 i 使得顶点上放置了一块 x_i,并将棋子移动到顶点 y_i (如果顶点上有两块 x_i,仅移动一)。允许将两个棋子放置在同一顶点上。
当玩家无法执行操作时,他/她就输了。 我们假设两名球员都发挥最佳状态。
其中 2^M 不同可能的图表为 G',有多少导致爱丽丝获胜? 求计数模数 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
输出
打印数量 G' 导致爱丽丝获胜,取模 10^9+7.
示例输入 1
2 1 1 2
示例输出 1
1
下图显示了两种可能的图表: G'。 标有○的图表导致爱丽丝获胜,标有×的图表导致鲍勃获胜。
示例输入 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