首先考虑判定一张强连通图，要缩点。缩点后一个点那么就是一张强连通图，是一个 DAG 就是一个非强连通图。单点条件很严苛，正难则反。如果我们已经知道每个点属于哪个强连通分量，那么做一次 DAG 子图计数就能计算出来不合法的方案数。问题在于我们不知道每个点属于哪个强连通分量。但是实际上我们并不在乎整个 DAG 的具体形态，而是只在乎“它是一个 DAG 而不是一个单点”。为了描述这件事情我们只需要找到一组入度为 0 的强连通分量即可，剩下的不用在乎。
先设 E_{S, T} 为 S 到 T 边数，H_S 为 S 内部边数。
令 $g_T$ 为形成奇数个强连通分量的方案数减去形成偶数个强连通分量。那么 $f_S = 2^{H_{S}} - \sum\limits_{T \subset S, T\not = \empty} g_T2^{E_{T, S - T} + H_{S - T}}$。现在对 $g$ 计算。如果没有容斥系数那么 $g_S = \sum\limits_{\operatorname{lowbit(S)}\in T\subset S}f_Tg_{S - T}$。现在有了容斥系数，奇偶数量变化，这些都要取反，特别的 $T = S$ 时 $f_T$ 不用取反。$g_S = f_S - \sum\limits_{\operatorname{lowbit}(T)\in T \subsetneq S} f_Tg_{S - T}$。我们发现很严重的事情在于是不是计算 $f_S$ 的时候要用到 $g_S$。但是 $g_S$ 中 $f_S$ 这部分代表的是 $S$ 全在一个连通分量中的方案数，在 $f$ 中是合法的，不应该减去。因此我们先处理 $g_S$，令此时 $f_S$ 为 $0$，然后再处理 $f_S$，最后把 $g_S$ 加上 $f_S$ 即可。
本来对于 $E$ 我是用 $O(3^n)$ 写的，但是因为我调用了 $O(3^n)$ 次 unordered_map 常数爆炸导致跑的还没还有 $O(n3^n)$ 快（悲。
```cpp
#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N = 15, Mod = 1e9 + 7;
il int lowbit(int x) {
return x & (-x);
}
il void upd(int &x, int y) {
x = (((x + y) >= Mod) ? (x + y - Mod) : (x + y));
}
int n, m, bas2[N * N + 10];
bool gra[N + 3][N + 3];
int H[(1 << N) + 10], out[(1 << N) + 10];
int f[(1 << N) + 10], g[(1 << N) + 10];
int E(int S, int T) {
int rest = 0;
while(S) {
int R = lowbit(S);
rest += __builtin_popcount(out[R] & T);
S -= R;
}
return rest;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
bas2[0] = 1;
for(int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
x--, y--;
bas2[i] = bas2[i - 1] * 2 % Mod;
gra[x][y] = 1;
for(int S = 0; S < (1 << n); S++)
if(((S >> x) & 1) && ((S >> y) & 1))
H[S]++;
out[(1 << x)] |= (1 << y);
}
for(int S = 1; S < (1 << n); S++) {
if(__builtin_popcount(S) == 1) {
f[S] = g[S] = 1;
continue;
}
for(int T = S - lowbit(S); ; T = (T - 1) & (S - lowbit(S))) {
int R = T + lowbit(S);
upd(g[S], (Mod - 1ll * f[R] * g[S - R] % Mod) % Mod);
if(!T) break;
}
f[S] = bas2[H[S]];
for(int T = S; T; T = (T - 1) & S)
upd(f[S], (Mod - 1ll * g[T] * bas2[E(T, S - T) + H[S - T]] % Mod) % Mod);
upd(g[S], f[S]);
}
cout << f[(1 << n) - 1] << endl;
}
```