Ultra-Meow

时间限制：2.5 秒
空间限制：256 MB

K1o0n 给你一个长度为 $n$ 的数组 $a$，由数字 $1, 2, \dots, n$ 组成。接受吗？当然！但拿它做什么？当然，计算 $\operatorname{MEOW}(a)$。

定义 $\operatorname{MEX}(S, k)$ 为不在集合 $S$ 中的第 $k$ 个正整数（严格大于零）按升序排列的值。再定义 $\operatorname{MEOW}(a)$ 为对数组 $a$ 的所有不同子集 $b$，求 $\operatorname{MEX}(b, |b| + 1)$ 的总和。

$\operatorname{MEX}(S, k)$ 的例子：

• $\operatorname{MEX}(\{3,2\}, 1) = 1$，因为 $1$ 是第一个不在集合中的正整数；
• $\operatorname{MEX}(\{4,2,1\}, 2) = 5$，因为前两个不在集合中的正整数是 $3$ 和 $5$；
• $\operatorname{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$。

输出格式

对于每组测试数据，输出一个整数 —— $\operatorname{MEOW}(a)$。由于答案可能很大，请将其对 $10^9 + 7$ 取模后输出。

样例输入

5
2
3
4999
5
1

样例输出

12
31
354226409
184
4