THE PROBLEM STATEMENT:

Emma was given a function definition by her teacher.The definition of the recursive function is given by the pseudo code below:
fun(n)
if n<=0:
return 1
else:
return fun(--n)+fun(n--)

She was asked to write down the value returned by this function modulo 1000000000 + 7, ie, fun(n)%1000000007. The teacher made it more difficult for Emma and asked her to evaluate this for many different values of (n).

INPUT:
The first line of input consists of positive integer t, the number of test cases. After this t lines follow each contain a positive integer n, for which the answer is to be calculated according to the function above.

OUTPUT:
The output has t lines, each per test case. Each line contains the answer for that particular test case.

CONSTRAINTS:
1<=t<=100000
0<=n<=10¹⁴