BUILDTOW  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
hide comments
ben:
20170215 02:37:08
100th :) 

surajmall:
20161017 20:21:38
good question teaches us a new important algo 

Deepak :
20160104 21:35:52
patterns in fibonacci numbers ;).. 

harshit sharma:
20150620 19:12:53
copy paste fibosum solution.... :P 

Vikrant Singh:
20150308 06:07:27
stupid '$' gave me 1 WA :P 

anshul garg:
20140524 12:03:22
Getting TLE!!


[Lakshman]:
20140524 09:31:49
@Ak Your algorithm complexity O( n )is too much for this problem and you are getting RTE because of too much recursion. curious? but how did you got AC? Last edit: 20140524 09:33:35 

`Ak:
20140524 07:30:10
pls help....


free mind ;):
20140306 11:56:47
easy one just like FIBOSUM !


Ankit Kumar:
20131222 01:00:57
@Rohan Phadke

Added by:  Saransh Bansal 
Date:  20120321 
Time limit:  0.323s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 