题目描述

级共有$n$ 位同学，依次以$1,2,...,n$ 标号。这$n$ 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有$m$ 对这样的关系（$m$ 是一个非负整数）。当$m\ge 1$ 时，第$i$ 对关系（$1\le i\le m$ ）给出$a_i,b_i$ ，表示排队时编号为$a_i$ 的同学需要排在编号为$b_i$ 的同学前面，并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对$10^9+7$ 取模的结果。

输入格式

第一行，两个整数$n,m$ ，分别表示同学们的数量与关系数量。
接下来$m$ 行，每行两个整数$a_i,b_i$，表示一对关系。



对于20%的数据，$n\le 100$,$k\le 100$,树的形态为一条链;
对于20%的数据，$n\le 1000$,$k=0$;
对于60%的数据，$n\le 1000$,$k\le 1000$;
对于全部数据，保证有$1\le n\le 1000$,$0\le k\le 1000$,$0\le a_i\le 1$ 。

输出格式

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

4 2
1 3
2 4

2

来源

https://bas.ssoier.cn/problem_show.php?pid=4104