简单题。
发现 \(m\) 很小，所以一个箱子可以用一个二进制数 \(a_i\) 表示，值域 \(w=2^{20}\)。然后就变成取出若干个 \(a_i\) 使得或起来为全集的方案数。
将所有 \(a_i\) 按位取反，即求若干个 \(a_i\) 与起来为空集的方案数，就是这题。
考虑容斥，令 \(t_{S}\) 为与起来恰为 \(S\) 的方案数，\(g_S\) 为与起来包含 \(S\) 的方案数。显然有 \(g_S=\sum\limits_{S\subseteq T}t_T\)，反演得到 \(t_{S}=\sum\limits_{S\subseteq T}(-1)^{|S|-|T|}g_T\)。由于我们要求 \(t_{\varnothing}\)，即为 \(\sum\limits_{T}(-1)^{|T|}g_T\)。由于可以 \(O(w)\) 枚举 \(T\)，我们现在考虑如何求 \(g\)。
由于与起来包含 \(S\)，所以你选出来每个数都包含 \(S\)，所以 \(g_S=2^{f_S}-1\)，\(f_S\) 为包含 \(S\) 的数的个数。
显然 \(f\) 是个超集和，想一下 FWT 求子集和的时候，把前面贡献后面，那么现在在后面贡献前面即可。
然后就做完了。复杂度 \(O(n+w\log w)\)。
const int maxn = 2e6 + 100;
const int lg = 20;
const int S = (1 << lg) - 1;
const int mod = 1e9 + 7;
int n, k, a[maxn], c[S + 100], f[S + 100], g[S + 100];
int qpow(int p, int q) {
int res = 1;
while (q) {
if (q & 1) res = 1ll * res * p % mod;
p = 1ll * p * p % mod, q >>= 1;
}
return res;
}
int main() {
n = read(), k = read();
for (int i = 1; i <= n; i++) {
int p = read();
for (int j = 1; j <= p; j++)
a[i] |= (1 << (read() - 1));
c[(1 << k) - 1 - a[i]]++;
}
for (int i = 0; i <= S; i++) f[i] = c[i];
for (int o = 2, k = 1; o <= (1 << lg); o <<= 1, k <<= 1)
for (int i = 0; i < S; i += o)
for (int j = 0; j < k; j++)
(f[i + j] += f[i + j + k]) %= mod;
for (int i = 0; i <= S; i++) g[i] = (qpow(2, f[i]) + mod - 1) % mod;
int ans = 0;
for (int i = 0; i <= S; i++) {
int t = __builtin_popcount(i), tp = (t & 1) ? (mod - 1) : 1;
(ans += 1ll * tp * g[i] % mod) %= mod;
}
write(ans);
return 0;
}