CF1992G.Ultra-Meow

K1o0n 给了你一个长度为 $n$ 的数组 $a$，其中包含数字 $1, 2, \ldots, n$。你接受吗？当然接受！但接下来要做什么呢？当然是计算 $\text{MEOW}(a)$。

设 $\text{MEX}(S, k)$ 表示集合 $S$ 中按升序缺失的第 $k$ 个正整数（严格大于零）。定义 $\text{MEOW}(a)$ 为对数组 $a$ 的所有不同子集 $b$，将 $\text{MEX}(b, |b| + 1)$ 求和。

以下是集合的 $\text{MEX}(S, k)$ 的一些例子：

• $\text{MEX}(\{3,2\}, 1) = 1$，因为 $1$ 是该集合中缺失的第一个正整数；
• $\text{MEX}(\{4,2,1\}, 2) = 5$，因为该集合中缺失的前两个正整数是 $3$ 和 $5$；
• $\text{MEX}(\{\}, 4) = 4$，因为空集没有任何数字，所以缺失的前 $4$ 个正整数是 $1, 2, 3, 4$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例一行，包含一个整数 $n$（$1 \le n \le 5000$），表示赠送数组的大小。

保证所有测试用例中 $n^2$ 的总和不超过 $25 \cdot 10^6$。

对于每个测试用例，输出一个整数，表示 $\text{MEOW}(a)$。由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

由 ChatGPT 4.1 翻译