배열 챌린지

시간 제한1초메모리 제한512 MB

요약

선형 점화식 h와 닫힌 형태의 배열 b, a가 주어질 때 n이 10^15까지 커질 수 있는 floor(sqrt(a_n))을 10^9+7로 나눈 나머지를 구한다.

문제

다음과 같이 정의되는 배열 $h$ 를 생각하자.

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*}$$ 또한 두 배열 $b$와 $a$를 아래와 같이 정의한다. $$\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*}$$ 주어진 정수 $n$에 대해 $\left\lfloor \sqrt{a_n} \right\rfloor$의 값을 구하라. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다 ( $1 \le T \le 1000$ ).

각 테스트 케이스는 정수 $n$ 을 포함하는 한 줄로 이루어진다 ( $2 \le n \le 10^{15}$ ).

각 테스트 케이스마다 문제의 답을 나타내는 정수 하나를 한 줄에 출력한다.