1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #include<bits/stdc++.h> #define int long long using namespace std; const int max_n=2000006,mod=1000000007; inline int read(){ int x=0;bool w=0;char c=getchar(); while(c<'0' || c>'9') w|=c=='-',c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return w?-x:x; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10^48); } inline int mi(int a,int p=mod-2){ int res=1; while(p){ if(p&1) res*=a,res%=mod; a*=a,a%=mod,p>>=1; } return res; }
int n,m,S,f[max_n],F[max_n],ans;
inline void OR(int *f,int x=1){ for(register int k=1,l=2;l<=S;l<<=1,k<<=1) for(register int i=0;i<S;i+=l) for(register int j=0;j<k;++j) f[i+j+k]+=f[i+j]*x%mod, f[i+j+k]=(f[i+j+k]+mod)%mod; }
signed main(){ n=read(),m=read(),S=(1<<m); for(register int i=1;i<=n;++i){ int k=read(),st=0; for(register int i=1;i<=k;++i){ int p=read()-1; st|=(1<<p); } ++f[st]; } OR(f); for(register int i=0;i<S;++i) F[i]=mi(2,f[i])-1; OR(F,-1); write(F[S-1]); return 0; }
|