P8757 [Lanqiao Cup 2021 NOI Qualifier A2] Perfect Sequence

Selecting some elements from a sequence and keeping their original order to form a new sequence is called a subsequence of the sequence. The value of a subsequence is the sum of all elements in the subsequence. If a sequence is monotonically decreasing, and every number except the first one is a factor of the previous number, then this sequence is called a perfect sequence. If a subsequence of a sequence is a perfect sequence, then it is called a perfect subsequence of the sequence. The length of the longest perfect subsequence of a sequence is called the perfect length of the sequence. Given a positive integer $n$, the maximum value of the perfect length among all permutations of $1$ to $n$ is called the $n$-th order maximum perfect length. Given a positive integer $n$, compute the sum of the values of all perfect subsequences whose length is exactly the $n$-th order maximum perfect length, over all permutations of $1$ to $n$.

Each test case contains multiple queries. The queries are independent of each other. The first line contains an integer $T$, representing the number of queries. The next $T$ lines each contain an integer $n$, representing the given $n$.

Output $T$ lines, in order, each corresponding to the answer for one query. Each line contains one integer, which is the remainder of the corresponding answer modulo $1000000007$ (i.e. $10^{9}+7$).

**Sample Explanation** When $n=1$, the answer is obviously $1$. When $n=2$, all permutations include $(1,2)$ and $(2,1)$. Among them, $(2,1)$ has the longest perfect subsequence, which is $(2,1)$ itself. The $2$-nd order maximum perfect length is $2$, so the answer is $2+1$. When $n=3$, all permutations include $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$. Among them, $(2,1)$ and $(3,1)$ are both longest perfect subsequences, and the $3$-rd order maximum perfect length is $2$. Sequences $(1,2,3)$ and $(1,3,2)$ have no perfect subsequence of length $2$. Sequence $(2,1,3)$ has the perfect subsequence $(2,1)$, with a total value sum of $3$. Sequence $(2,3,1)$ has perfect subsequences $(2,1)$ and $(3,1)$, with a total value sum of $7$. Sequence $(3,1,2)$ has the perfect subsequence $(3,1)$, with a total value sum of $4$. Sequence $(3,2,1)$ has perfect subsequences $(2,1)$ and $(3,1)$, with a total value sum of $7$. The answer is $3+7+4+7=21$. **Constraints and Notes** For $10\%$ of the testdata, $n \leq 10$. For $20\%$ of the testdata, $n \leq 20$. For $30\%$ of the testdata, $T \leq 20, n \leq 1000$. For $40\%$ of the testdata, $T \leq 20, n \leq 10^{5}$. For all testdata, $1 \leq T \leq 10^{5}, 1 \leq n \leq 10^{6}$. Lanqiao Cup 2021, Second Round Provincial Contest, Group A, Problem J. Translated by ChatGPT 5