Vaibhav is very lazy . He does not like solving the questions which consists of irrelevant story. So he solves only straightforward questions. So, he comes across such a question.

Given:
F(0) = 1, F(1) = 1;
F(n) = F(n-1) + F(n-2) + (3ⁿ)*n

Given T test cases each containing an integer N. Find F(N)%(1000000007)

CONSTRAINTS

$1 \leq T \leq 10^{5}$

$1 \leq N \leq 10^{18}$