题意：

给定一个长度为 $n$ 的数组，选择它的一个子序列（不一定要连续的），问有多少种选法使得它们 AND 的值的二进制表示法中有 $k$ 个 $1$。

思路：

这个题就是一个简单的 DP，

设 $f_{i,j}$ 表示选择到了第 $i$ 个数字（但不一定是把前 $i$ 个数字都选择了），所有被选择的数字的 AND 值等于 $j$ 的方案数。

那么我可以不选择这个数字：$f_{i,j} = f_{i,j} + f_{i-1,j}$，即与选择 $i - 1$ 个数字，数字的 AND 的值为 $j$ 的方案数一样。

那么我们也可以选择这个数字：$f_{i,j\& a_i} = f_{i,j\& a_i} + f_{i - 1,j}$，即从前 $i - 1$ 个数得到的 $j$ 与上一个 $a_i$ 就有前 $i$ 个数字得到的 $j\&a_i$。

当然，我们为什么一定要让第 $i$ 个数字受到前面的数字的影响呢？我们可以另起炉灶！即 $f_{i, a_i}=1$。

这就讨论完了所有情况。

归纳总结起来就是

$$\begin{cases} f_{i,j} = f_{i,j} + f_{i-1,j} \\ f_{i,j\& a_i} = f_{i,j\& a_i} + f_{i - 1,j} \\ f_{i, a_i}=1 \\ \end{cases} $$

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, mod = 1e9 + 7;

int f[N][64];
int n, k;
int a[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) memset(f[i], 0, sizeof(f[i]));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i][a[i]] = 1;
        for (int j = 0; j < 64; j++) {
            f[i][j] = (1ll * f[i][j] + f[i - 1][j]) % mod;
            f[i][j & a[i]] = (1ll * f[i][j & a[i]] + f[i - 1][j]) % mod;
        }
    }
    int res = 0;
    for (int i = 0; i < 64; i++) {
        int cnt = 0;
        for (int j = 0; j < 6; j++) {
            if (i >> j & 1) cnt++;
        }
        if (cnt == k) res = (1ll * res + f[n][i]) % mod;
    }
    cout << res << '\n';
}

int main() {
    #ifdef DEBUG
    freopen("Test.in", "r", stdin);
    cout << "===================START===================" << endl;
    #endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();

    #ifdef DEBUG
    cout << "====================END====================" << endl;
    #endif
    return 0;
}