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