Build the Tower
8. Build the Tower
The president of Yanyang University has decided to build a new tower in front of the auditorium and has invited the students of SCE to help with the project. The tower is one of a kind and is made up of N cuboids one over the other. Each cuboid has a height of 1 unit and the length and breadth of a cuboid is equal. The top most cuboid’s length is 1 unit. The cuboid below it has a length of 2. All the cuboids below it have their lengths equal to the sum of the lengths of the 2 cuboids above it.
|
Cuboid |
Length |
Breadth |
Height |
|
1 |
1 |
1 |
1 |
|
2 |
2 |
2 |
1 |
|
3 |
3 |
3 |
1 |
|
4 |
5 |
5 |
1 |
|
5 |
8 |
8 |
1 |
As a token of appreciation the president has decided to give SCE a grant of
$ ((Volume of Tower) % 1000000007)
Your task is to calculate the amount of grant received by SCE for a given value of N.
Input
The first line contains the number of test cases (T) followed by T lines each containing a single integer N.
Output
For each test case output the grant that SCE receives for building the tower.
Constraints
T <= 20, N <= 10^18
Example
Sample Input
2 5 10
Sample Output
$103 $12815