The great pirate Luffy and his crew are in the search of the treasure “One Piece”. On their journey through the sea, they met Kaido, one of the four Great Emporers of the Sea.

Instead of fighting they decided to play a game of sequence and series, And it was decided that Kaido will ask the questions and Luffy will answer them.

Since he is one of the smartest and best Pirate he knows his way around fitting the best Algorithms. But Luffy knows nothing about programming, so he asks you to solve the problems for him and he will give you some part of his treasure when he finds it.

Kaido gives Luffy a number N and Luffy knows that if he finds S(N) it will give him the basic idea to solve the problem.

Luffy also knows that f(N) is the sum of elements of all the possible subsets of numbers till N.

For an example f(2) = (1+2+1+2) where the possible subsets of N = 2 are (1) , (2) & (1,2)

Zoro one of Luffy's crew members found out the relationship between S(N) and f(N). S(N) equals to sum of all f(x) such that 1 ≤ x ≤ N Ex: - S(5) = f(1) + f(2) + f(3) + f(4) + f(5)

NOTE: - Since the answer can be very large print the answer modulo 1000000000 +7.

Input Format

The first line of the input contains T, specifying the number of test cases. Next each of the T lines contains an integer N, specifying the number which is given to Luffy by Kaido.

Constraints

1 ≤ T ≤ 10^5

1 ≤ N ≤ 10^9

Output Format

You need to output the value of S(N).

Time Limit : 1sec

Sample Input

3

1

2

3

Sample Output

1

7

31

Explanation

..

Author - Amil Khare