Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Selection

By YouKnowWho · Limits 1s, 512 MB

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

InputOutput
1
3
22

Discussion

Statistics


67% Solution Ratio

mohanr7073Earliest, 7M ago

failed_coderFastest, 0.1s

mohanr7073Lightest, 1.2 MB

SwampFireShortest, 765B

Submit

Login to submit