HS08FOUR - 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.


Added by:Robert Gerbicz
Date:2009-04-05
Time limit:1s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League 2008/09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.