시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 41 | 31 | 18 | 78.261% |
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.
3 4 7 9
1255 324725 13185773