Fair Advantage#12786
There are contestants taking part in a competition. The -th contestant has a strength s_i with 1\le s_i\le n, and all strengths are pairwise distinct, so the multiset of strengths is exactly \{1,2,\dots,n\}.
The contestants must be divided into two teams. Every contestant belongs to exactly one team. The advantage of a team whose members have strengths T_1,T_2,\dots,T_m is
The organizers want the match to be as fair as possible, that is, they want the two advantages to be as close to each other as possible. Formally, if and are the two teams and \operatorname{adv}(A)\ge \operatorname{adv}(B), they want to minimize the ratio
Only splittings for which this ratio is an integer are considered valid.
For each given , determine the minimum possible ratio . Since the answer may be very large, print it modulo 10^{9}+7.
For n=1 the answer is assumed to be .
The first line contains a single integer (1\le t\le 10^{4}) — the number of test cases.
The only line of each test case contains a single integer (1\le n\le 10^{6}) — the number of participants.
It is guaranteed that the sum of over all test cases does not exceed 10^{6}.
For each test case print a single integer — the minimum ratio between the team with the higher advantage and the team with the lower advantage, modulo 10^{9}+7.
Beware that the ratio itself grows far beyond the range of a -bit integer type, so all computations must be carried out modulo 10^{9}+7 (and intermediate products must be reduced before they overflow).
Example 1
In the first test case (n=1) there is a single contestant, and the answer is by definition.
In the second test case (n=2) the only splitting is and , which yields \tfrac{2}{1}=2.
In the third test case (n=4) the best splitting is the following:
which yields an answer of
In the fourth test case (n=6) the best splitting is \{2,5,6\} and \{1,3,4\}, which yields