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