题目描述

小杨所在班级有 n 位同学（编号1~n），需要排成一列队伍。其中有 m 对同学必须相邻且顺序固定（ai 必须在 bi 前面）。求所有可能的排队方式数量，结果对 10⁹+7 取模。

输入格式

• 第一行：n（同学数量），m（约束条件数量）
• 接下来 m 行：每行 ai, bi，表示 ai 必须排在 bi 前面且相邻

输出格式

一个整数，表示合法排队方式的数量（模 10⁹+7）

样例

输入样例 1

4 2
1 3
2 4

输出样例 1

2

输入样例 2

3 0

输出样例 2

6

数据范围

• 20% 数据：1 ≤ n ≤ 8，0 ≤ m ≤ 10
• 20% 数据：1 ≤ n ≤ 10³，0 ≤ m ≤ 1
• 100% 数据：1 ≤ n ≤ 2×10⁵，0 ≤ m ≤ 2×10⁵