题意：有n个点和m条限制，每条限制限制了一个点的度数不能为某个数。
求合法的树的个数模10^9+7
n<=10^6
m<=17
思路：WYZ作业
首先m<=17显然是2^m容斥
枚举每一个限制有用或没用，考虑某一个约束情况下的方案数
Caylay定理：n个点的生成树的个数=n^(n-2)
Prufer序列：一个长度为n-2的Prufer序列对应唯一的一棵n个节点的树，度数为a[i]的点在其中出现了(a[i]-1)次
考虑先在序列中填上所有的受约束条件的点，它们的方案数是C(n-2,a[1]-1)*C(n-2-(a[1]-1),a[2]-1)*……
化简得：
(n-2)!/((a[1]-1)!(a[2]-1)!……*(n-2-sigma(a[i]-1))!)
考虑没有约束的点可以随意在剩下的序列中出现，它们的方案数为：
(n-p)^(n-2-sigma(a[i]-1))
其中p为选中的约束条件个数
将两部分相乘，根据p的奇偶性进行容斥计算即可
几个hack点：
1.对于同一个点可能会有多个约束条件，需要判断某一个点是否被多次限制，如果被多次限制就不能计入答案
2.n=1需要特判ans=1（真的吗，这个点可是坑了我5点头盾）
const mo=;
var flag:array[..]of longint;
fac,exf:array[..]of int64;
a,b,c:array[..]of longint;
n,m,i:longint;
sun:int64; function mult(x,y:longint):int64;
var tmp:int64;
begin
tmp:=x; mult:=;
while y> do
begin
if y and = then mult:=mult*tmp mod mo;
tmp:=tmp*tmp mod mo;
y:=y>>;
end;
end; procedure dfs(k:longint);
var i,j,tot,sum:longint;
ans:int64;
begin
if k=m+ then
begin
tot:=; ans:=fac[n-]; sum:=n-;
for i:= to m do
if c[i]> then
begin
inc(tot);
inc(flag[a[i]]);
sum:=sum-(b[i]-);
end;
for i:= to m do
if (c[i]>)and(flag[a[i]]>) then
begin
for j:= to m do
if c[j]> then dec(flag[a[j]]);
exit;
end;
for i:= to m do
if c[i]> then ans:=ans*exf[b[i]-] mod mo;
//writeln(sum);
if sum>= then
begin
ans:=ans*exf[sum] mod mo;
ans:=ans*mult(n-tot,sum) mod mo;
if tot and = then sun:=(sun+ans) mod mo
else sun:=(sun-ans) mod mo;
sun:=(sun+mo) mod mo;
end;
for i:= to m do
if c[i]> then dec(flag[a[i]]);
exit;
end;
if b[k]= then dfs(k+)
else
begin
c[k]:=;
dfs(k+);
c[k]:=;
dfs(k+);
end;
end; begin
assign(input,'51nod1806.in'); reset(input);
assign(output,'51nod1806.out'); rewrite(output);
readln(n,m);
if n= then
begin
writeln();
exit;
end;
for i:= to m do read(a[i],b[i]);
exf[]:=; exf[]:=; fac[]:=;
for i:= to do fac[i]:=fac[i-]*i mod mo;
for i:= to do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo;
for i:= to do exf[i]:=exf[i-]*exf[i] mod mo;
dfs();
writeln(sun);
close(input);
close(output);
end.