Chiaki 수열 다시 보기

Chiaki는 무한 수열 $a_1, a_2, a_3, ...$에 관심이 있다. 이 수열은 다음과 같이 정의된다.

$a_n=\begin{cases}1 & n = 1,2 \\ a_{n - a_{n-1}} + a_{n-1 - a_{n-2}} & n \ge 3\end{cases}$

Chiaki는 이 수열의 처음 $n$개 항의 합, 즉 $\sum\limits_{i=1}^{n}a_i$를 알고 싶어 한다. 이 값은 매우 클 수 있으므로 Chiaki는 $10^9 + 7$로 나눈 나머지에만 관심이 있다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 정수 $T$ ($1 \le T \le 10^5$)가 주어지며, 이는 테스트 케이스의 수이다. 각 테스트 케이스마다:

첫 줄에 정수 $n$ ($1 \le n \le 10^{18}$)이 주어진다.

각 테스트 케이스마다 답을 나타내는 정수를 출력한다.