考虑 dp。设 \(f_S\) 为点集 \(S\) 构成强连通分量的方案数。
容易想到容斥。设 \(ed_S\) 为 \(S\) 内部连边数，那么 \(f_S\) 就是总的方案数 \(2^{ed_S}\) 减去构成的不是强连通分量的方案数。
我们考虑如果整个图不是一个强连通分量，那么缩点后一定有 \(> 1\) 个分量，并且缩完点后图变成一个 DAG。
由此我们想到钦定 \(T \subseteq S\) 为点集 \(T\) 是入度为 \(0\) 的所有强连通分量点集的并集（注意这里 \(T\) 可以 \(= S\)，因为可以有 \(> 1\) 个入度为 \(0\) 的强连通分量）。
但是这样会有算重，因为我们无法保证 \(T\) 中的分量就一定是全部入度为 \(0\) 的强连通分量。考虑容斥，容斥系数为 \((-1)^{cnt - 1}\)，其中 \(cnt\) 为强连通分量个数，表示选奇数个强连通分量的系数为 \(+1\)，偶数个为 \(-1\)。
设 \(g_T\) 为 \(T\) 中分成奇数个分量的方案数减去分成偶数个分量的方案数。容易转移：\(g_T = -\sum\limits_{w \subset T} f_w g_{T \setminus w}\)。注意这里我们钦定 \(w\) 包含 \(T\) 的最低位。
那么 \(f_S\) 就能转移了。设 \(h_T\) 为边 \(u \to v\) 的数量，其中 \(u \in S, v \in T\)，那么这个东西可以递推求出。我们要限制其他点不能向 \(T\) 中的点连边，那么 \(f_S = 2^{ed_S} - \sum\limits_{T \subset S} 2^{ed_S - h_T} g_T\)。
code
// Problem: #37. 【清华集训2014】主旋律
// Contest: UOJ
// URL: https://uoj.ac/problem/37
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 220;
const int maxm = (1 << 15) + 50;
const ll mod = 1000000007;
ll n, m, in[maxn], pw[maxn], f[maxm], g[maxm], h[maxm], ed[maxm], lg[maxm];
int stk[maxm], top;
pii E[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 0; i < n; ++i) {
lg[1 << i] = i;
}
pw[0] = 1;
for (int i = 1; i < maxn; ++i) {
pw[i] = pw[i - 1] * 2 % mod;
}
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
--u;
--v;
in[v] |= (1 << u);
E[i] = make_pair(u, v);
}
for (int S = 1; S < (1 << n); ++S) {
for (int i = 1; i <= m; ++i) {
int u = E[i].fst, v = E[i].scd;
if ((S & (1 << u)) && (S & (1 << v))) {
++ed[S];
}
}
}
for (int S = 1; S < (1 << n); ++S) {
f[S] = pw[ed[S]];
for (int T = S; T; T = (T - 1) & S) {
stk[++top] = T;
}
while (top) {
int T = stk[top--];
h[T] = h[T ^ lowbit(T)] + __builtin_popcount(in[lg[lowbit(T)]] & S);
}
for (int T = (S - 1) & S; T; T = (T - 1) & S) {
if (T & lowbit(S)) {
g[S] = (g[S] - f[T] * g[S ^ T] % mod + mod) % mod;
}
}
for (int T = S; T; T = (T - 1) & S) {
f[S] = (f[S] - pw[ed[S] - h[T]] * g[T] % mod + mod) % mod;
}
g[S] = (g[S] + f[S]) % mod;
}
printf("%lld\n", f[(1 << n) - 1]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}