Description

一个序列中取出一些元素按照原来的顺序排列成新的序列称为该序列的一个子序列。子序列的价值为子序列中所有元素的和。

如果一个序列是单调递减的，而且除了第一个数以外的任何一个数都是上一个数的因数，则称这个序列为一个完美序列。

一个序列中的一个子序列如果是完美序列，则称为该序列的一个完美子序列。一个序列的最长完美子序列长度，称为该序列的完美长度。

给定正整数 $n$，$1$ 至 $n$ 的所有排列的完美长度的最大值，称为 $n$ 阶最大完美长度。

给定正整数 $n$，请求出 $1$ 至 $n$ 的所有排列中长度正好为 $n$ 阶最大完美长度的所有完美子序列的价值的和。

Input Format

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$, 表示询问数。

接下来 $T$ 行, 每行包含一个整数 $n$, 表示一个给定的 $n$ 。

Output Format

输出 $T$ 行，依次对应每组询问的答案。

每行包含一个整数，表示对应的答案除以 $1000000007$（即 $10^{9}+7$）的余数。

5
1
2
3
5
10

1
3
21
140
2268000

Hint

【样例说明】

当 $n=1$ 时，答案显然是 $1$ 。

当 $n=2$ 时, 全排列包括 $(1,2)$ 和 $(2,1)$, 其中 $(2,1)$ 拥有最长的完美子序列, 也就是 $(2,1)$ 本身, $2$ 阶最大完美长度为 $2$，答案即为 $2+1$ 。

当 $n=3$ 时，全排列包括 $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(2,3,1)$、$(3,1,2)$、$(3,2,1)$ 。其中 $(2,1)$ 和 $(3,1)$ 都是最长的完美子序列，$3$ 阶最大完美长度为 $2$。

序列 $(1,2,3)$ 和 $(1,3,2)$ 中没有长度为 $2$ 的完美子序列。

序列 $(2,1,3)$ 中有完美子序列 $(2,1)$，价值和为 $3$。

序列 $(2,3,1)$ 中有完美子序列 $(2,1)$ 和 $(3,1)$，价值和为 $7$。

序列 $(3,1,2)$ 中有完美子序列 $(3,1)$，价值和为 $4$。

序列 $(3,2,1)$ 中有完美子序列 $(2,1)$ 和 $(3,1)$,价值和为 $7$。

答案为 $3+7+4+7=21$ 。

【评测用例规模与约定】

对于 $10 \%$ 的评测用例，$n \leq 10$;

对于 $20 \%$ 的评测用例，$n \leq 20$;

对于 $30 \%$ 的评测用例，$T \leq 20, n \leq 1000$;

对于 $40 \%$ 的评测用例，$T \leq 20, n \leq 10^{5}$;

对于所有评测用例，$1 \leq T \leq 10^{5}, 1 \leq n \leq 10^{6}$。

蓝桥杯 2021 第二轮省赛 A 组 J 题。