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}}\\ $