HS08FOUR - Four colors

no tags 

Let there be given n points: P1,P2...,Pn arranged in this order on a line. We would like to color them using four colors: white, black, red, and blue, in such a way that for every three consecutive points it is true that either
1. the colors of these three points are pairwise distinct, or
2. the color of some point is white.

Input

An integer T, denoting the number of testcases (T<100000). In each line you are given one positive integer ( n<1000000000 ). There are 5 input sets.

Output

Find the number of possible colorings of the n points. Since the answer can be very big, output only the answer modulo 1000000007.

Example

Input:
4
1
2
3
1000

Output:
4
16
43
283570349

Warning: large input/output data, be careful with certain languages

Warning: A naive algorithm will probably solve only the first input set.


hide comments
Francky: 2014-12-17 02:28:48

AC at first try and rank #1 with 0.17s. It won't be easy to take it. Many thanks for this problem, I would have make such a problem, I didn't see it before.
Now, I'll try to do better, if I can.

abdou_93: 2014-12-15 11:56:52

not easy to get accepted

Zhouxing Shi: 2013-12-11 10:33:51

passed with 5*5 matrix!!

ymGXX: 2010-11-16 02:10:45

Great problem!

刘启鹏: 2010-07-08 12:43:14

nice problems :)

.:: Pratik ::.: 2009-08-13 18:28:34

I have AC with 4*4 ( see 1e5 cases )
Good luck, try to avoid mod.

Time limit is super strict (but that is common with this author who has super fast solutions)

Oleg: 2009-08-13 18:13:09

Can I ask another hint? do you have 4*4 matrix or reduced it to 3*3 or less ?

Oleg: 2009-08-13 18:12:08

Yes, this is what I tried. I precomputed all low (1024) combintations, mid(1024) and high (1024) - so have only 3 multiplication. still TL :(

.:: Pratik ::.: 2009-08-13 17:38:26

Lot of optimizations are needed to get accepted.

( HINT : reduce matrix multiplications with some (many) precomputations )


Added by:Robert Gerbicz
Date:2009-04-05
Time limit:0.161s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:High School Programming League 2008/09