Leo would like to play with some really big numbers, OK...

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21, so FIB(FIB(6))=21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are an integer N.

Output

For each test case, print FIB(FIB(N)) ,
as the answer could not fit in a 64bit container,
give your answer modulo 1000000007.

Example

Input:
3
0
5
6

Output:
0
5
21

Constraints

1 <= T <= 10^4
0 <= N <= 10^100

Time limit is set to allow (sub-optimal) 500B of python3 code to get AC.
A near optimal solution is within 0.02 and 0.04s with a fast language, and around 1s in Python2 without psyco.

Edit(20/I/2015) With Cube cluster, it is not hard to get 0.0s with fast languages, and my old code ended in 0.08s using PY3.4.

Edit(11-2-2017) With compiler update, new TL. My old Python code ends in 0.04s, and it's easy to get 0.00s using a fast language.