题目背景

2024 年 12 月 GESP C++ 八级编程第 2 题

题目描述

小杨所在班级共有 $n$ 位同学，依次以 $1,2,ldots,n$ 标号。这 $n$ 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。

共有 $m$ 对这样的关系。第 $i$ 对关系给出 $a_i,b_i$，表示排队时编号为 $a_i$ 的同学需要排在编号为 $b_i$ 的同学前面，并且两人在队伍中相邻。

请计算满足所有关系的排队方式数量。由于答案可能很大，只需要输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行输入两个整数 $n,m$，分别表示同学数量与关系数量。 接下来 $m$ 行，每行输入两个整数 $a_i,b_i$，表示一对相邻且有先后顺序的关系。

输出格式

输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

4 2
1 3
2 4

2

3 0

6

3 2
1 2
2 1

0

数据范围与提示

• 对于 $20\%$ 的测试点，保证 $1 \le n\le 8$，$0 \le m\le 10$。
• 对于另外 $20\%$ 的测试点，保证 $1 \le n\le 10^3$，$0 \le m\le 1$。
• 对于全部测试点，保证 $1 \le n\le 2 imes 10^5$，$0 \le m\le 2 imes 10^5$，$1 \le a_i,b_i \le n$。

来源

GESP 2024 年 12 月 C++ 八级 T2