4313. [清华集训 2014]主旋律

【题目背景】

年年考，年年错（

【题目描述】

给你一个 $n$ 个点 $m$ 条边的有向图 $G=(V,E)$，保证无重边自环。

求 $E'\subseteq E$ 的 $E'$ 个数，满足 $G'=(V,E')$ 是一个强联通图。

答案对 $10^9+7$ 取模。

【输入格式】

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示一条 $u\to v$ 的有向边

【输出格式】

一行一个整数，表示答案。

【样例输入】

5 15
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1

【样例输出】

9390

【数据规模与约定】

对于 $20\%$ 的数据满足: $n \leq 5$；

对于 $50\%$ 的数据满足: $n \leq 8$；

对于 $70\%$ 的数据满足: $n \leq 10$；

对于 $100\%$ 的数据满足: $n \le 15, 0 \le m \leq n(n - 1)$。

【来源】

清华集训 2014。