HS08FOUR  Four colors
Let there be given n points: P_{1},P_{2}...,P_{n} 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:
20141217 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.


abdou_93:
20141215 11:56:52
not easy to get accepted


Zhouxing Shi:
20131211 10:33:51
passed with 5*5 matrix!! 

ymGXX:
20101116 02:10:45
Great problem! 

刘启鹏:
20100708 12:43:14
nice problems :) 

.:: Pratik ::.:
20090813 18:28:34
I have AC with 4*4 ( see 1e5 cases )


Oleg:
20090813 18:13:09
Can I ask another hint? do you have 4*4 matrix or reduced it to 3*3 or less ? 

Oleg:
20090813 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 ::.:
20090813 17:38:26
Lot of optimizations are needed to get accepted.

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