You are given \(T\) tests and each test contains a number \(n\). Your task is to determine the value of the following expression: 

\(\Huge\displaystyle\sum_{i=0}^{n} [F(i)]^{2}\)

\(F(0)=0,\ F(1)=1,\ F(2)=1,\ ...,\ F(n) = F(n-1)+F(n-2)\) 

Input format

• The first line contains a number \(T\) .
• Next \(T\) lines contain \(T\) queries.

Output format

Print the answer as described in the problem mod \(1e9+7\).

Constraints

\({1 \le T \le 10^5}\\ {1 \le N \le  10^{18}}\\ \)