You are given an integer \(N\) . Find the value of the following function \(F(N)\)

\(F(N) = 2*F(N-1) + 3*F(N-2) + N^{2}*3^{N} , modulo (10^{9}+7)\)
Also , \(F(0) = 1 \) and \(F(1) = 1\)

INPUT FORMAT

First line will contain \(T\) - number of test cases

\(T\) following lines will contain an integer \(N\)

OUTPUT FORMAT

For each test case, print the value of \(F(N) modulo (10^{9} + 7)\)

CONSTRAINTS 

\(1 \leq T \leq 10^{3}\)
\(1 \leq N \leq 10^{18} \)