Problem Description

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$.

Input Format

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 Format

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$).

5
1
2
3
5
10

1
3
21
140
2268000

Hint

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