1396. 拓扑排序

给定有向无环图,求出满足这样条件的路径的数量:

  • 起点入度为 00
  • 终点出度为 00

答案对 8011200280112002 取模。

输入

第一行,两个正整数 n,m (1n5×103,1m5×105)n,m \ (1 \leq n \leq 5 \times 10^3, 1 \leq m \leq 5 \times 10^5),结点数量和边的数量。

接下来 mm 行,每行两个正整数 u,v (1u,vn)u,v \ (1 \leq u,v \leq n),表示 uuvv 有一条边。

输出

一个整数,表示答案。

样例

标准输入 复制文本
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
标准输出 复制文本
5
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 120
通过 51