给定有向无环图,求出满足这样条件的路径的数量:
答案对 801120028011200280112002 取模。
输入
第一行,两个正整数 n,m (1≤n≤5×103,1≤m≤5×105)n,m \ (1 \leq n \leq 5 \times 10^3, 1 \leq m \leq 5 \times 10^5)n,m (1≤n≤5×103,1≤m≤5×105),结点数量和边的数量。
接下来 mmm 行,每行两个正整数 u,v (1≤u,v≤n)u,v \ (1 \leq u,v \leq n)u,v (1≤u,v≤n),表示 uuu 到 vvv 有一条边。
输出
一个整数,表示答案。
样例
5 7 1 2 1 3 2 3 3 5 2 5 4 5 3 4
5