You are given $t$ test cases. Each test case contains an integer $n$. Find the value of the following function:

such that 

• $f[0] = 0, f[1]=1, f[2]=1 ,....,f[n]=f[n-1]+f[n-2].$

Formally, you are required to find the summation from $i=0$ to $i=n$ for ${f[i]}$.

Input format

• The first line contains an integer $t$ denoting the number of test cases.
• Each of the next $t$ lines contains an integer $n$.

Output format

Print the answer as described above modulo $10^9+7$.

Constraints

$1 \le   t  \le  10^5$

$1 \le  n  \le {10^{18}}$