排队

题目描述

⼩杨所在班级共有 位同学，依次以 标号。这 位同学想排成⼀⾏队伍，其中有些同学之间关系⾮常 好，在队伍⾥需要排在相邻的位置。具体来说，有 对这样的关系（ 是⼀个⾮负整数）。当 时，第 对关 系（ ）给出 ，表⽰排队时编号为 的同学需要排在编号为 的同学前⾯，并且两⼈在队伍中相邻。 现在⼩杨想知道总共有多少种排队⽅式。由于答案可能很⼤，你只需要求出答案对 取模的结果。

输入格式

第⼀⾏，两个整数 ，分别表⽰同学们的数量与关系数量。 接下来 ⾏，每⾏两个整数 ，表⽰⼀对关系。

输出格式

⼀⾏，⼀个整数，表⽰答案对 取模的结果。

样例输入 #1

4 2
1 3
2 4

样例输出 #1

2

样例输入 #2

3 0

样例输出 #2

1 6
3.2.9 输入样例 3
1 3 2
2 1 2
3 2 1
3.2.10 输出样例 3
1 0

数据范围

对于 20% 的测试数据点，保证 ， 。 对于另外 20% 的测试数据点，保证 ， 。 对于所有测试数据点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。