You are given a sequence whose \(n^\text{th}\) term is
\[T_n=n^2-(n-1)^2\]
You have to evaluate the series
\[S_n=T_1+T_2+T_3+...+T_n\]
Find \(S_n \bmod (10^9+7)\).
Input Format
The first line of input contains \(T\), the number of test cases.
Each test case consists of one line containing a single integer \(n\).
Constraints
\(1\leq T\leq 10\)
\(1\leq n\leq 10^{16}\)
Output Format
For each test case, print the required answer in a line.
Sample Input
2
2
1
Sample Output
4
1
Explanation
Case 1: We have \(4=1+3\)
Case 2: We have \(1=1\)
Solution
When we solve this problem under the congruence relation modulo \(m:= 10^9+7\), we can easily come up with the following derivation, which surprisingly reduces to a very simple term.
\[ \begin{array}{rl} S_n \equiv & \sum\limits_{k=1}^n T_k \pmod{m}\\ \equiv & \sum\limits_{k=1}^n (k^2 - (k-1)^2) \pmod{m}\\ \equiv & \sum\limits_{k=1}^n (k^2 - (k^2-2k+1)) \pmod{m}\\ \equiv & \sum\limits_{k=1}^n (2k-1) \pmod{m}\\ \equiv & 2\sum\limits_{k=1}^n k-n \pmod{m}\\ \equiv & n(n+1)-n \pmod{m}\\ \equiv & n^2 \pmod{m}\\ \equiv & (n \bmod m) (n\bmod m) \pmod{m}\\ \end{array} \]
The last step of the derivation is needed as the constraint limits \(n\) to at most \(10^{16}\), which squared would need \(1+\lfloor \log_2((10^{16})^2)\rfloor = 1+\lfloor 32\log_2(10)\rfloor=108\) bit. But even with the modulos, a bigint number would be needed to store the maximum number of \(\gt 10^{18}\). Implementing an own modpow function, which has logarithmic runtime and solves the problem in 32bit is quite trivial. However, a similar algorithm is used with Python's pow-function extension, which adds a modular exponentiation. But since we use Python, which has infinite integer precision, and since the exponent is just 2, we can ignore the elaborated facts. Bringing the whole thing to life then reveals:
t = int(input())
for i in range(0, t):
n = int(input())
print(n * n % 1000000007)