题目描述

有 $n$ 个两两不同的节点，编号为 $1,2,\dots,n$。你需要在它们之间连接恰好 $n-1$ 条无向边，使得整张图成为一棵树。

但是给出了 $m$ 个限制条件。第 $i$ 个限制给出一对 $(u_i,d_i)$，表示 节点 $u_i$ 的度数不能等于 $d_i$。

节点的度数指与该节点相连的边的条数。

请问满足所有限制条件的生成树方案数有多少？答案对 $1000000007$ 取模。

输入格式

第一行两个整数 $n,m$，表示节点个数与限制个数。

接下来 $m$ 行，每行两个整数 $u_i,d_i$，表示限制：节点 $u_i$ 的度数不能为 $d_i$。

输出格式

输出一行一个整数，表示满足条件的方案数（对 $1000000007$ 取模）。

数据范围与保证

• $1 \le n \le 10^6$
• $0 \le m \le 17$
• $1 \le d_i \le n-1$
• 保证不会有两条完全相同的限制（即不存在相同的 $(u_i,d_i)$）
• 为了方便起见，保证 $1 \le u_i \le m$（因此被限制的点都在前 $m$ 个点里），并且显然也有 $u_i \le n$

样例 1

3 1
1 2

2

解释：$n=3$ 时一共有 $3$ 棵不同的树（边集分别为 ${(1,2),(1,3)}$、${(1,2),(2,3)}$、${(1,3),(2,3)}$）。其中第二棵里节点 $1$ 的度数是 $2$，违反“节点 $1$ 的度数不能为 $2$”，所以合法的只有 $2$ 种。