题目描述

给定一张包含 $n$ 个点、$m$ 条有向边的有向无环图（$DAG$），点从 $1$ 到 $n$ 编号。
定义“拓扑排序”为将所有点排成一个序列，使得对于每条有向边 $(u \to v)$，在序列中 $u$ 必须出现在 $v$ 之前。

请计算该图不同拓扑排序的数量，答案对 $10^9 + 7$ 取模。

输入格式

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

输出格式

输出一个整数，表示拓扑排序方案数对 $10^9 + 7$ 取模的结果。

输入输出样例

输入 #1

3 2
1 2
1 3

输出 #1

2

解释：
可行的拓扑序为 $[1,2,3]$、$[1,3,2]$。

输入 #2

10 17
4 1
1 2
5 1
5 10
7 4
5 3
6 3
6 8
10 2
4 2
6 9
7 10
10 8
6 5
3 10
7 9
1 8

输出 #2

450

数据范围

• $1 \le n \le 20$
• $0 \le m \le \frac{n(n-1)}{2}$
• 保证点编号在 $[1,n]$

子任务