题目描述

给定一个无边权有向无环图 $G$。我们考虑用深度优先搜索来计算从节点 $1$ 到节点 $N$ 的最短路长度。具体运行如下伪代码：

viz[x] = 0, 对所有 x
dist[1] = 0

DFS(node):
    viz[node] = 1
    for node 的邻接表中的每个邻居 v:
        if viz[v] == 0:
            dist[v] = dist[node] + 1
            DFS(v)

DFS(1)
输出 dist[N]

图的邻接表按照输入边的顺序建立：

lista[x] = [], 对所有 x
读入 n, m
for i = 1..m:
    读入 a, b
    把 b 加到 lista[a] 的末尾

显然，这个 DFS 算法不一定能得到真正的最短路，因为访问顺序取决于输入中边的排列顺序。

例如，如果构建图时先读入边 $(1\to2)$，再读入边 $(1\to3)$，那么 DFS 访问节点 $1$ 的邻居时会先访问 $2$，再访问 $3$。不同的边输入顺序可能导致 DFS 得到不同的 dist[N]。

现在给定图 $G$ 的全部 $M$ 条边。请计算在这 $M!$ 种边的排列顺序中，有多少种排列会使上述 DFS 输出从 $1$ 到 $N$ 的真正最短路长度。

答案对 $1\,000\,000\,007$ 取模。

输入格式

第一行包含两个整数 $N,M$，表示节点数和边数。

接下来 $M$ 行，每行包含两个整数 $x,y$，表示图中有一条从 $x$ 到 $y$ 的有向边。

输出格式

输出一个整数，表示可接受的边排列数量对 $1\,000\,000\,007$ 取模后的结果。

数据范围与限制

• $1 \le N \le 100000$；
• $1 \le M \le 200000$；
• 对于 10% 的测试，$N,M\le 10$；
• 对于 25% 的测试，$N\le 20, M\le 60$；
• 对于 60% 的测试，$N\le 1400, M\le 4000$；
• 保证每条边不会重复出现；
• 保证每条边至少属于一条从 $1$ 到 $N$ 的路径。

样例输入1

3 3
1 2
1 3
2 3

样例输出1

3

样例解释

能得到最短距离的三种边排列为：

(1->3) (1->2) (2->3)
(1->3) (2->3) (1->2)
(2->3) (1->3) (1->2)

样例输入2

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

样例输出2

90

样例解释

从 $1$ 到 $4$ 的真正最短距离为 $2$，共有 $90$ 种边排列会使 DFS 得到该距离。

样例输入3

7 11
2 4
3 2
1 3
2 6
6 7
4 5
4 6
6 5
5 7
2 5
3 4

样例输出3

24948000