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.
