Madhav went to Riya's Birthday Party. He was a geek so he had no idea regarding which gift she'l like.
So he took an array of integers with him. The array followed a particular order. First element of array is 1.
Second element of array is 6.
Other elements of the array are two less than the mean of the number preceding and succeeding it.
As it is obvious, Riya felt that this idea was stupid and hence she wanted to punish Madhav.
She decided to ask Madhav the nth number of the array. If he tells the wrong answer, she would slap him.
Help Madhav to escape from this embarrassing situation.

Input:

The input starts with T, the number of Test Cases.
Next T lines contain integer N.

Output:

For each test case, output an integer which is the N^th number of the array. As the answer can be very large, output it modulo 10⁹+7

Constraints:

1 ≤ T ≤ 10⁵
1 ≤ N ≤ 10¹⁸