19102번 - Array Challenge 다국어

문제

Consider an array $h$ such that its elements are defined as follows:

$$\begin{eqnarray*} h_0 & = & 2 \text{,} \\ h_1 & = & 3 \text{,} \\ h_2 & = & 6 \text{,} \\ h_n & = &4 h_{n - 1} + 17 h_{n - 2} - 12 h_{n - 3} - 16 \text{ for $n \ge 3$.} \\ \end{eqnarray*}$$

Additionally, let us define two arrays $b$ and $a$ as shown below:

$$\begin{eqnarray*} b_n & = & 3 h_{n + 1} h_n + 9 h_{n + 1} h_{n - 1} + 9 h_n^2 + 27 h_n h_{n - 1} - 18 h_{n + 1} - 126 h_n - 81 h_{n - 1} + 192 \text{ for $n > 0,ドル and} \\ a_n & = & b_n + 4^n \text{ for $n > 0$.} \\ \end{eqnarray*}$$

Your task is to find the value $\left\lfloor \sqrt{a_n} \right\rfloor$ for a given integer $n$. As the answer could be very large, print it modulo 10ドル^9 + 7$.

입력

The first line of input contains an integer $T,ドル the number of test cases (1ドル \le T \le 1000$).

Each test case consists of a single line containing an integer $n$ (2ドル \le n \le 10^{15}$).

출력

For each test case, print a single line with a single integer: the answer to the problem.

제한

힌트