It is a dream of each engineering student to be freed from the compulsion of attending the lectures.

Such a constraint is not applicable to Gupta, a student of No Attendance Institute of Technology.

According to their academic calendar, He needs to decide number of classes that he'll be attending in a N day schedule. Being lazy, he doesn't wishes to attend lectures on two consecutive days.Only one lecture will be scheduled per day.

You need to tell the number of ways in which he can schedule the N day plan. Note that staying absent for all the days will be still counted as a possible plan.

Input:

The first line contains T, the number of test cases.

Each test case contains a number N denoting the number of days.

Output

Each test case contains a single number denoting the number of ways by which the N-day plan may be completed.

Output your answer modulo 10^9+7.

Constraints:

1 <= T <= 60000

1 <= N <= 10^18