Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #include <algorithm>
- #include <string>
- #include <set>
- #include <map>
- #include <vector>
- #include <queue>
- #include <iostream>
- #include <iterator>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <sstream>
- #include <fstream>
- #include <ctime>
- #include <cstring>
- #pragma comment(linker, "/STACK:66777216")
- using namespace std;
- #define pb push_back
- #define ppb pop_back
- #define pi 3.1415926535897932384626433832795028841971
- #define mp make_pair
- #define x first
- #define y second
- #define pii pair<int,int>
- #define pdd pair<double,double>
- #define INF 1000000000
- #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
- #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
- #define all(c) (c).begin(), (c).end()
- #define SORT(c) sort(all(c))
- #define rep(i,n) FOR(i,1,(n))
- #define rept(i,n) FOR(i,0,(n)-1)
- #define L(s) (int)((s).size())
- #define C(a) memset((a),0,sizeof(a))
- #define VI vector <int>
- #define ll long long
- #define MOD 1000000007
- int a,b,c,d,i,j,n,m,k;
- int g[1 << 20], p2[1 << 20];
- int main() {
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- scanf("%d%d", &n, &m);
- rept(i, n) {
- scanf("%d", &b);
- c = 0;
- rept(j, b) {
- scanf("%d", &a);
- c |= 1 << (a - 1);
- }
- ++g[c];
- }
- rept(i, m)
- rept(mask, 1 << m)
- if (mask & 1 << i) g[mask] += g[mask ^ 1 << i];
- p2[0] = 1;
- rep(i, n) {
- p2[i] = p2[i - 1] * 2;
- if (p2[i] >= MOD) p2[i] -= MOD;
- }
- int ans = 0;
- rept(mask, 1 << m) {
- c = 0;
- rept(i, m) if (mask & 1 << i) ++c;
- if ((m + c) % 2) ans -= p2[g[mask]]; else
- ans += p2[g[mask]];
- if (ans < 0) ans += MOD;
- if (ans >= MOD) ans -= MOD;
- }
- printf("%d\n", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement