Love for Hinata

4.5

2 votes
Easy
Problem

You always wondered why Hinata is soooo cute.
You couldn't stop dreaming about her.
Hinata's cuteness keeps on increasing every day, rapidly.

enter image description here

One day after doing lots of research on Hinata, you developed a formula to estimate her cuteness quotient.
On the Nth day Hinata's cuteness can be calculated as the product of first N fibonacci numbers.

Fib(1)=1;
Fib(2)=1;
Fib(i)=Fib(i-1)+Fib(i-2)

But this product can be very large (Hinata is just too much cute to be expressed) ,
so you have to calculate this value over modulo 1000000007(10^9+7).

For example :
On 4th day Hinata's cuteness will be :
Cuteness = Fib(1) * Fib(2) * Fib(3) * Fib(4) = 1 * 1* 2 * 3 = 6
Cuteness = 6 % 1000000007 = 6

To impress Hinata , You want to develop and gift this cuteness predciction software to her.
She will be happy , as everyone admires their own beauty .
Will you make her happy ?

Input :

First line will contain an integer T (number of testcases).
Each of the testcases contains an integer N.

Output :

For each testcase print the required answer on a new line.

Constraints :

1<=T<=200000
1<=N<=200000

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?