← 返回题目列表

Codeforces · 1992/G

G. 超喵

中文机器翻译题面 查看原题

K1o0n 给了你一个长度为 $$$n$$$ 的数组 $$$a$$$,由数字 $$$1, 2, \ldots, n$$$ 组成。接受吗?当然!但该怎么办呢?当然,计算$$$\text{MEOW}(a)$$$。

设 $$$\text{MEX}(S, k)$$$ 为集合 $$$S$$$ 中不存在的按升序排列的第 $$$k$$$ 个正整数(严格大于零)。将 $$$\text{MEOW}(a)$$$ 表示为 $$$\text{MEX}(b, |b| + 1)$$$ 在数组 $$$a$$$ 的所有不同子集 $$$b$$$ 上的总和。

集合的 $$$\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$$$ 取模。

示例

输入 #1

5
2
3
4999
5
1

输出 #1

12
31
354226409
184
4