我觉得这题需要对图计数有非常深刻的理解。

首先，考察这个有向图博弈的 SG 函数，那么原限制相当于 。

考虑计数 的方案数，再用总数减去不合法。

序列本身并没有什么眼前一亮的性质，唯一能入手计数的地方就是它的定义：。

考虑钦定 序列 ，然后从小到大枚举 ，考察所有 的点，那么其有如下限制：

1. 对于任意 ，每个 的点必须 的点连至少一条边
2. 的点之间两两都不能连边 。
3. 的点可以任意连向 的边。

既然是从小到大考虑的 ，我们不妨选出 的集合 ，那么对于剩下的点，将所有的 减去 ，我们发现剩下的点的导出子图是个相似的子问题！

所以设 表示仅考虑点集 的导出子图， 的方案数。枚举 的子集 ，显然 和 要么都属于 ，要么都不属于 。然后考虑 和 之间的连边。对于 中的点，其必须向 中的点至少连一条边，对于 中的点，其可以向 中的任意点连边。 中的点两两之间都不能连边。处理一些辅助数组，可以将转移做到 。

#include <bits/stdc++.h>
using namespace std;
const int N = 20,M = 255,Sz = 1 << 15,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m;
int cnt[Sz][N],e[N][N];
int dp[Sz];
int Pow2[M];
int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;i++) {
		int u,v;
		cin >> u >> v;
		e[u][v] = 1;
	}
	for(int u = 1;u <= n;u++) {
		for(int i = 1;i <= n;i++) cnt[1 << i - 1][u] = e[u][i];
		for(int S = 0;S < (1 << n);++S)
			cnt[S][u] = cnt[S & (S - 1)][u] + cnt[S & (-S)][u];
	}
	Pow2[0] = 1;
	for(int i = 1;i <= m;i++) Pow2[i] = (Pow2[i - 1] + Pow2[i - 1]) % P;
	for(int S = 1;S < (1 << n);++S)  {
		dp[S] = 1;
		for(int T = S;T;T = (T - 1) & S) if((T & 1) == (T >> 1 & 1)) {
			int zro = S ^ T,coef = 1;
			for(int i = 1;i <= n;i++) {
				if((T >> i - 1) & 1) coef = 1ll * coef * (Pow2[cnt[zro][i]] - 1) % P;
				if((zro >> i - 1) & 1) coef = 1ll * coef * Pow2[cnt[T][i]] % P;
			}
			Plus(dp[S],1ll * dp[T] * coef % P);
		}
	}
	int ans = (Pow2[m] - dp[(1 << n) - 1] + P) % P;
	cout << ans << endl;
	return 0;
}