Chacha got a perfect 10 pointer last semester. He was very happy. His roommate Micro asked him for a big party but he simply refused for it. So angry Micro took his grade sheet and threatened him that if he don't give a big party, he will burn it. So Chacha gave him a big party and they both lived happily ever after. Now forget about that story and solve the following problem. Given a function f(i,j) =Number of submatrices in which (i,j)th cell of an N*N matrix lies.
Find ∑i,j f (i,j) for all i,j ϵ {1, 2, 3...,N}. Since answer can be very large print answer modulo 10^9+7
Input:
First line consists of an integer T denoting the number of test cases.
Each test case consists of only one line containing an integer which denotes N, the order of matrix.
Output:
Print the output of each test case in a new line.
Constraints:
1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^18
Colored area in the following matrices shows the 4 submatrices in which cell (1,1) will be lying.
So, f(1,1)=4
Similarly f(1,2)=4, f(2,1)=4, f(2,2)=4
So, f(1,1)+f(1,2)+f(2,1)+f(2,2)=16.
