SUST has n departments numbered from 1 to n where every pair of distinct departments is connected by a unique road. The cost of the road from city i to city j is i * j.
The VC of SUST doesn't like redundant roads. So he will select the minimum number of roads in such a way that it is possible to visit every department from any other department using only the selected roads. The cost of this selection is the summation of costs of all of the selected roads.
As there are different ways of a selection, now he wants to find the sum of costs of all possible selections. As this number may be large, he wants its remainder modulo (109+7). Two ways are considered different if there is at least one road that is selected in one selection but not in the other.
Input
The first line will contain an integer t(1 ≤ t ≤ 105), the number of test cases.
Each of the next t lines will contain an integer n(2 ≤ n ≤ 1018), the number of departments in SUST.
Output
Output the sum of costs of all possible selections modulo (109+7).
Sample
| Input | Output |
|---|---|
1 3 | 22 |
