题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，求有多少种删去若干边的方案使得剩余的图强连通。

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

输入格式

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

接下来 $m$ 行，每行两个整数 $a,b$ 表示一条边 $a\to b$。

数据保证不存在 $a=b$ 或两条边的起点和终点都相同。

输出格式

一行一个整数表示方案数对 $10^9+7$ 取模后的值。

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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 15$，$0\leq m\leq n(n-1)$。

来源

$2015$ 年国家集训队测试。