题目描述

大家都知道那家销售热门游戏“Deni Monopoly”的保加利亚公司。公司管理层决定寻找一个新 logo，并打算把所有员工都画进去。为此，他们需要给员工安排一个顺序，使得不存在某个员工被排在其任意一个直接下属之后的情况。

由于公司规模很大，满足条件的排列可能有很多，因此首先需要知道这样的排列一共有多少种。这个重要任务被交给了公司里最优秀的程序员 Deni。但很不巧，她最近工作太多，没有时间完成这件事，于是她请求你编写一个名为 monopoly 的程序来帮助她。

由于经历了大量重组并采用了最“先进”的管理方式，这家公司的组织结构可以说相当奇特。不过它仍然满足下面两个正常性质：

• 每个非普通员工都有若干名下属员工；
• 不存在某个员工的某个下属（不一定是直接下属）反过来又成为他的上级（也不一定是直接上级）的情况。

而重组带来的奇怪之处则体现在：

• 一个员工可以有多个直接上级；
• 若某个员工的直接上级为 $x_1, x_2, \dots, x_k$，那么存在 $1,2,\dots,k$ 的一个排列 $i_1,i_2,\dots,i_k$，使得若按顺序写成$$x_{i_1}, x_{i_2}, \dots, x_{i_k},$$ 则 $x_{i_1}$ 是 $x_{i_2}$ 的上级（不一定是直接上级），$x_{i_2}$ 是 $x_{i_3}$ 的上级，……，$x_{i_{k-1}}$ 是 $x_{i_k}$ 的上级。

Deni 会给出由 $N$ 名员工和 $M$ 条关系构成的公司结构，并要求你求出满足条件的员工排列数量。员工编号为 $1$ 到 $N$。

由于答案可能很大，你只需要输出它对 $10^9+7$ 取模后的结果。

输入格式

第一行输入两个正整数 $N$ 和 $M$，分别表示员工数和关系数。

接下来 $M$ 行，每行输入两个整数 $x$ 和 $y$，表示编号为 $x$ 的员工是编号为 $y$ 的员工的直接上级（相应地，$y$ 是 $x$ 的直接下属）。

输出格式

输出一个整数，表示满足条件的员工排列数量对 $10^9+7$ 取模后的结果。

数据范围

• $1 \le N \le 100000$
• $1 \le M \le 200000$

子任务

只有通过某一子任务中的全部测试点，才能获得该子任务的分数。

样例 1

输入

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

输出

8

说明

有多个直接上级的员工是 3 和 4。

• 3 的直接上级是 2 和 1。若按顺序排列为 1, 2，则 1 是 2 的上级；
• 4 的直接上级是 3 和 2。若按顺序排列为 2, 3，则 2 是 3 的上级。

因此所有满足条件的排列共有 8 种：

• 1 2 3 6 4 5
• 1 2 3 6 5 4
• 1 2 3 4 5 6
• 1 2 3 4 6 5
• 1 2 3 5 6 4
• 1 2 3 5 4 6
• 1 2 6 3 4 5
• 1 2 6 3 5 4

样例 2

输入

4 2
1 2
3 4

输出

6

说明

这里所有满足条件的排列共有 6 种：

• 1 2 3 4
• 1 3 2 4
• 1 3 4 2
• 3 1 2 4
• 3 1 4 2
• 3 4 1 2