BUILDTOW - Build the Tower

no tags 

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: 2017-02-15 02:37:08

100th :)

surajmall: 2016-10-17 20:21:38

good question teaches us a new important algo

Deepak : 2016-01-04 21:35:52

patterns in fibonacci numbers ;)..

harshit sharma: 2015-06-20 19:12:53

copy paste fibosum solution.... :P

Vikrant Singh: 2015-03-08 06:07:27

stupid '$' gave me 1 WA :P

anshul garg: 2014-05-24 12:03:22

Getting TLE!!
My solution is O(logn).
Submission Id :: 11636338
Please help

[Lakshman]: 2014-05-24 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: 2014-05-24 09:33:35
`Ak: 2014-05-24 07:30:10

pls help....
getiing runtime error(SIGSEGV) :(
http://ideone.com/YEujzQ

free mind ;): 2014-03-06 11:56:47

easy one just like FIBOSUM !
@akhil for (10^18)-1 =712534868 !

Ankit Kumar: 2013-12-22 01:00:57

@Rohan Phadke
Your program fails for n>20 as fib[20] has only 20 elements while in the loop
for(j=0;j<height;j++)
{sum=sum+fib[j];.....}
your prog will access fib[20],fib[21]... which doesn't exist so it will give a runtime error
PS : Your whole approach is wrong here even though you fix the above problem..


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