spoj#HS08FOUR. Four colors
Four colors
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.