Description
听着自己美妙的曲子，小Z进入了梦乡。在梦中，小Z仿佛又回到了自己纵横考场的年代。在梦中，小Z参加了一场考试，这场考试一共有n道题，每道题的最终得分都是一个大于等于0的整数。然而醒来后，小Z忘记了自己每道题的得分。他只记得自己计算过m次一些题目的分数和，每道题都被计算过，并且只被计算过一次。除此之外他还记得其中t道题的满分分别是多少（一道题的得分不会超过满分）。现在小Z想知道他这场考试有多少种得分情况（至少有一道题的得分不同就算不同的情况），因为这个答案可能很大，你只需要输出答案对1,000,000,007取模后的结果即可。
Input
第一行两个整数n,m表示题目个数与求和次数。 接下来m行，每行以一个整数k开头，表示小Z这次对k道题进行了求和。然后k个整数a1~ak，表示这次求和的都是哪些题。最后一个整数c表示求和后的结果。 一行一个整数t，含义见题目描述。 t行，每行两个整数r,L，表示第r道题的满分是L。
Output
一行一个整数表示答案模1,000,000,007的结果。
Sample Input
5 2 2 1 2 5 3 3 4 5 7 1 3 4
Sample Output
180
Data Constraint
对于30%的数据：n,c≤8。 对于另外40%的数据：t=0。 对于100%的数据：1≤n,m≤1,000,000，0≤c,L≤1,000,000，0≤t≤20。
题解
没有限制时，显然可以直接组合数 当有限制时，发现限制数量很少，所以考虑使用容斥来解决这个问题 对于一个子要求a[i]<r（不满足），可以把它看成满足a[i]>=r,那么可以把a[i]分解为x+r+1的形式（x>0）这样就可以直接用没有限制的方法求出总的方案数
贴代码
const md=1000000007;var a,go:array[0..1000005]of longint; cc,tt:array[0..1000005]of longint; f:array[0..1100005]of int64; yu:array[0..2000005]of int64; p:array[0..25,1..2]of longint; i,j,k,l,m,n,x,y,z,t,o,c:longint; zong,ans,tot,tmp:int64;function quickmi(x,y:int64):int64;var a,b:int64;begin a:=x; b:=1; while y>0 do begin if y mod 2=1 then b:=(b*a) mod md; a:=(a*a) mod md; y:=y div 2; end; exit(b);end;begin //assign(input,'t3.in'); reset(input); assign(input,'equation.in'); reset(input); assign(output,'equation.out'); rewrite(output); readln(n,m); yu[0]:=1; yu[1]:=1; for i:=2 to 2000000 do yu[i]:=(yu[i-1]*i) mod md; z:=0; zong:=1; for i:=1 to m do begin read(k); cc[i]:=k; for j:=1 to k do begin read(a[z]); go[a[z]]:=i; end; readln(tt[i]); tmp:=(yu[k-1]*yu[tt[i]]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+tt[i]-1]) mod md; zong:=(zong*tmp) mod md; end; readln(t); for i:=1 to t do readln(p[i,1],p[i,2]); f[0]:=zong; ans:=zong; for i:=1 to 1<<t-1 do begin z:=1; for j:=1 to t do if i and (1<<(j-1))<>0 then z:=z*(-1); for j:=1 to t do if i and (1<<(j-1))<>0 then begin c:=tt[go[p[j,1]]]; l:=i xor (1<<(j-1)); for k:=1 to t do if (go[p[k,1]]=go[p[j,1]]) and (j<>k) then begin c:=(c-p[k,2]-1) mod md; if c<0 then break; end; if c<0 then continue; k:=cc[go[p[j,1]]]; tmp:=(yu[k-1]*yu[c]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+c-1]) mod md; tmp:=quickmi(tmp,md-2); c:=(c-p[j,2]-1) mod md; if c<0 then continue; f[i]:=(f[l]*tmp) mod md; tmp:=(yu[k-1]*yu[c]) mod md; tmp:=quickmi(tmp,md-2); tmp:=(tmp*yu[k+c-1]) mod md; f[i]:=(f[i]*tmp) mod md; ans:=(ans+z*f[i]+md) mod md; break; end; end; writeln(ans); close(input); close(output);end.
