题目理解

我们有一个初始集合 $S$，包含 $n$ 个互不相同的正整数。
初始分数为 $1$。
每次操作：

• 令 $m = \min(S)$
• 分数 $\times m$
• 从 $S$ 中删除 $m$
• 将 $1,2,\dots,m-1$ 全部加入 $S$（不会产生重复）

执行恰好 $k$ 次操作（保证集合非空），求最终分数对 $10^9+7$ 取模。

---

第一步：转化为二进制表示

为了方便，先将所有数减 $1$（因为操作中涉及 $1$ 到 $m-1$，减 $1$ 后变为 $0$ 到 $m-2$）。
设集合 $S$ 对应一个二进制数：

$$f(S) = \sum_{v \in S} 2^v$$

操作效果：

• 找到最低位 $b$（即最小值 $m = b+1$）
• 将 $\le b$ 的所有位翻转（因为 $0$ 到 $b$ 这些数要么被删除，要么被加入）
• 实际上，这正是二进制数减 $1$ 的操作：
  最低位 $b$ 从 $1$ 变 $0$，所有更低位从 $0$ 变 $1$。

因此：

$$f(S') = f(S) - 1$$

重要结论：

• 每次操作，$f(S)$ 减少 $1$。
• 从 $f(S)$ 到 $f(S) - 2^m$ 需要 $2^m$ 步，因为要逐次减 $1$ 经过中间值。

特别地，要将最小值 $m$（即二进制第 $m-1$ 位）完全移除，需要恰好 $2^{m-1}$ 次操作？
等一下，注意：如果最小值是 $m$（原始值），对应二进制位是 $m-1$。
那么 $f(S)$ 包含 $2^{m-1}$ 这一项。
要使这一位变为 $0$，需要从 $2^{m-1}$ 一直减到 $0$，共 $2^{m-1}$ 步。
但题解中写的是 $2^v$，其中 $v = m-1$，所以是一致的。

---

第二步：计算 $F(v)$ —— 完整移除最小值 $v+1$ 的贡献

设 $F(v)$ 表示：当最小值为 $v+1$（即二进制位 $v$ 为 $1$）时，执行 $2^v$ 次操作（刚好移除这个最小值）所累积的分数乘积。

模拟过程：

• 第一次操作：最小值 $v+1$ 被移除，分数乘 $v+1$，然后加入 $0,1,\dots,v-1$。
• 之后，这些新加入的数会依次作为最小值被移除。
  移除顺序：先移除 $0$（需要 $2^0=1$ 步，贡献 $F(0)=1$ 倍），再移除 $1$（需要 $2^1=2$ 步，贡献 $F(1)$），依此类推。

实际上，移除 $v$ 的过程是：
执行一次操作（乘 $v+1$），然后递归处理 $0$ 到 $v-1$ 这些更小的数。

因此：

$$F(0) = 1$$ $$F(v) = (v+1) \cdot \prod_{j=0}^{v-1} F(j)$$

这个递推可以直接预处理到 $v=30$（因为 $2^{30} > 10^9$，$k$ 最大 $10^9$）。

---

第三步：模拟 $k$ 次操作

将初始 $S$ 中的每个数减 $1$ 后排序。
设当前要处理的最小值为 $v$（原始 $v+1$）。

情况 1：$k \ge 2^v$

我们可以完整移除这个最小值，消耗 $2^v$ 步，分数乘 $F(v)$，$k$ 减少 $2^v$，然后继续处理下一个最小值。

情况 2：$k < 2^v$

此时无法完全移除 $v$。我们需要计算：当前最小值为 $v$，还剩 $k$ 步，最终乘积是多少？
定义 $P(v, k)$ 为：当 $S$ 中只有 $v$ 和所有小于 $v$ 的数（且 $v$ 是当前最小值），剩余 $k$ 步（$k < 2^v$）时的乘积。

边界：$P(v, 0) = 1$。

转移：
第一步必须操作一次，乘 $v+1$，然后 $v$ 被移除，集合变成包含 $0,1,\dots,v-1$。
之后，我们从 $w=0$ 开始依次处理这些新元素（因为它们会依次成为最小值）：

• 如果 $k \ge 2^w$：可以完整移除 $w$，乘 $F(w)$，$k$ 减少 $2^w$。
• 否则 $k < 2^w$：进入子问题 $P(w, k)$，然后停止（因为更大 $w$ 不会影响）。

注意：$k$ 在第一步后已经减 $1$。

所以：

$$P(v, k) = (v+1) \cdot \text{process\_children}(v-1, k-1) $$

其中 $\text{process\_children}(v, k)$ 表示从 $w=0$ 到 $v$ 依次处理。

由于 $2^{30} > 10^9$，当 $w \ge 30$ 时，$2^w > k$ 必然成立，所以递归深度不超过 $30$。

---

第四步：算法实现

1. 预处理 $F[0..30]$。

2. 对每个测试用例：

   • 读入 $n,k$，将 $s_i$ 减 $1$，排序。
   • 遍历 $s$：
     • 若 $v \le 30$ 且 $k \ge 2^v$：$k -= 2^v$，$ans *= F[v]$。
     • 否则：$ans *= P(v, k)$，跳出循环。
   • 输出 $ans$。

3. $P(v, k)$ 递归实现：

   • 若 $k == 0$ 返回 $1$。
   • $ans = v+1$，$k--$。
   • 对 $w = 0$ 到 $v-1$（注意 $v$ 本身已被移除）：
     • 若 $k \ge 2^w$：$k -= 2^w$，$ans *= F[w]$。
     • 否则：$ans *= P(w, k)$，返回 $ans$。
   • 返回 $ans$。

---

第五步：复杂度

• 预处理 $F$：$O(30^2)$
• 每个测试用例：排序 $O(n \log n)$
• 递归 $P$：每次最多 $30$ 层，每层循环 $O(30)$，总 $O(30^2)$
• 总复杂度 $O(\sum n \log n + t \cdot 900)$，满足约束。

---

最终代码（C++，与标程一致）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
long long F[31];

long long P(int v, long long k) {
    if (k == 0) return 1;
    long long res = v + 1;
    k--;
    for (int w = 0; w < v; w++) {
        if (k >= (1LL << w)) {
            k -= (1LL << w);
            res = res * F[w] % MOD;
        } else {
            res = res * P(w, k) % MOD;
            break;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    F[0] = 1;
    for (int i = 1; i <= 30; i++) {
        F[i] = i + 1;
        for (int j = 0; j < i; j++) {
            F[i] = F[i] * F[j] % MOD;
        }
    }
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long k;
        cin >> n >> k;
        vector<int> s(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            s[i]--;
        }
        sort(s.begin(), s.end());
        
        long long ans = 1;
        for (int i = 0; i < n; i++) {
            int v = s[i];
            if (v <= 30 && k >= (1LL << v)) {
                k -= (1LL << v);
                ans = ans * F[v] % MOD;
            } else {
                ans = ans * P(v, k) % MOD;
                break;
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}