시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 5 2 66.667%

## 문제

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.

## 예제 입력 1

3
4
7
9


## 예제 출력 1

1255
324725
13185773