K1o0n gave you an array 𝑎 of length 𝑛, consisting of numbers 1,2,…,𝑛. Accept it? Of course! But what to do with it? Of course, calculate MEOW(𝑎).
Let MEX(𝑆,𝑘) be the 𝑘-th **positive** (strictly greater than zero) integer in ascending order that is not present in the set 𝑆. Denote MEOW(𝑎) as the sum of MEX(𝑏,|𝑏|+1), over all **distinct** subsets 𝑏 of the array 𝑎.
Examples of MEX(𝑆,𝑘) values for sets:
- MEX({3,2},1)=1, because 1 is the first positive integer not present in the set; - MEX({4,2,1},2)=5, because the first two positive integers not present in the set are 3 and 5; - MEX({},4)=4, because there are no numbers in the empty set, so the first 4 positive integers not present in it are 1,2,3,4.
Input
The first line contains a single integer 𝑡𝑡 (1≤𝑡≤10^4) — the number of test cases.
In a single line of each test case, an integer 𝑛 (1≤𝑛≤5000) is entered, the size of the array of gifted numbers.
It is guaranteed that the sum of 𝑛^2 over all test cases does not exceed 25⋅10^6.
Output
For each test case, output a single number — MEOW(𝑎). Since it may be very large, output it modulo 10^9+7.
题意
函数 MEX(S,k) 代表升序正整数列中第 k 个不属于集合 S 的数。
例：MEX([1,2,4],2)=5，MEX([2,3],1)=1，MEX([],1)=1
现在给你一个正整数列 S=1,2,…,n ，求出 ∑s∈SMEX(s,∣s∣+1)， 其中 ∣s∣ 为 s 的大小。
解法
记 S 的长度为 n ， s 的长度为 l ，前 l+1 个不属于集合 s 的升序正整数列为 t ， m=MEX(s,∣s∣+1)=MEX(s,l+1)=max(x)x∈t ，以下分情况讨论：
对于长度满足 2∗l+1≤n 的子序列，其 m 值不固定，对于给定的 l 中每个可能的值 m∈[l+1,2∗l+1] ，m 即为 t 序列的最大值， m 左侧有 m−1 个空位，在其中放入长度为 l 的 t 剩余序列和长度为 m−1−l 的 s 序列，排列个数为 (m−1l) ，m 右侧有 n−m 个空位，在其中放入长度为 l−(m−1−l) 的 s 剩余序列，排列个数为 (n−ml−(m−1−l))，故每个 m 值的排列个数为 (m−1l)∗(n−ml−(m−1−l))，这部分的 m 总和为 ∑l=02∗l+1≤n∑m=l+1m≤2∗l+1m∗(m−1l)∗(n−ml−(m−1−l))
对于长度满足 2∗l+1>n 的子序列，序列 s 和序列 t 的总长度超过 n ， 则其 m 值固定为 2∗l+1 ，长度为 l 的子序列的个数为 (nl) ，这部分的 m 总和为 ∑2∗l+1>nl≤n(2∗l+1)∗(nl)
