Description:


wangyurzee有 \(n\) 个各不相同的节点,编号从 \(1\)\(n\) 。wangyurzee想在它们之间连 \(n-1\) 条边,从而使它们成为一棵树。
可是wangyurzee发现方案数太多了,于是他又给出了 \(m\) 个限制条件,其中第 \(i\) 个限制条件限制了编号为 \(u[i]\) 的节点的度数不能为 \(d[i]\)
一个节点的度数,就是指和该节点相关联的边的条数。
这样一来,方案数就减少了,问题也就变得容易了,现在请你告诉wangyurzee连边的方案总数为多少。
答案请对 \(1000000007\) 取模。

样例解释
总方案共有3种,分别为{(1,2),(1,3)},{(1,2),(2,3)},{(2,3),(1,3)}。其中第二种方案节点1的度数为2,不符合要求,因此答案为2。

Input:


第一行输入 \(2\) 个整数 \(n\) ( \(1\le n\le 1000000\) ), \(m\) ( \(0\le m\le 17\) )分别表示节点个数以及限制个数。
\(2\) 行到第 \(m+1\) 行描述 \(m\) 个限制条件,第 \(i+1\) 行为 \(2\) 个整数 \(u[i], d[i]\) ,表示编号为 \(u[i]\) 的节点度数不能为 \(d[i]\)
为了方便起见,保证 \(1\le u[i]\le m\) 。同时保证 \(1\le u[i]\le n, 1\le d[i]\le n-1\) ,保证不会有两条完全相同的限制。

Output:


输出一行一个整数表示答案。

Sample Input:


Sample Output:


题解:


看到这个题可以很明显的想到容斥原理,然后我们只要计算确定某一些节点度数后树的数目。

我们可以考虑Prufur序列,因为它唯一对应一棵树,并且和度数有关。

然后我们可以发现树的数目就是在 \(n-2\) 的序列中把确定度数的节点选出来,然后剩下的乱选。

树的数目是:

\[\frac{(n-2)!}{(d[i_1]-1)!(d[i_2]-1)!\cdots (d[i_k]-1)!(n-2+k-\sum d)!}\times (n-k)^{n-2+k-\sum d}\]

然后计算一下就可以了。