405431: GYM101962 C Renan and Cirque du Soleil

Renan was driving the Cirque Du Soleil artists in his blue towner. Unfortunately the towner rolled over in Paralela (a well known avenue in Soteropolis). The $$$N$$$ circus performers have each a distinct value between $$$1$$$ and $$$N$$$. During the rollover the performers left the towner through the window, while doing some acrobatics and leaving poor Renan by himself inside the vehicle.

Everyone knows that Paralela is the habitat of an infamous Jaguar. This Jaguar wants to ambush the performers and get some food. Let $$$S$$$ be the value of satisfaction of its lunch. $$$S$$$ follows a totally arbitrary formula that can be calculated as shown below:

where $$$P$$$ is the set of performers $$$\{1, 2, \dots, N\}$$$, $$$\max(T)$$$ is the maximum value in $$$T$$$ and $$$\min(T)$$$ is the minimum value in $$$T$$$.

Renan feels like he could be in trouble, so he wants to know the satisfaction the Jaguar will get by ambushing the performers. Since Renan is not good at maths, you need to calculate $$$S$$$ for him. Note that this value can be big, so you only need to output it $$$S$$$ module $$$10^9 + 7$$$.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^{4}$$$), the number of testcases to be processed.

Each of the following $$$T$$$ lines contains an integer $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$) – the number of performers Renan was driving with him.

Output $$$T$$$ lines, one for each testcase. In every line you need to print the value of $$$S$$$ module $$$10^9 + 7$$$ for such testcase.

4
2
3
7
5

1
6
522
72