Statement:
Barry is working out in the Speed Lab. You, Cisco, his friend need to ensure that the power supply of the Lab, generated from the internal Nuclear Reactor is sufficient enough.
The Nuclear Reactor is powered by binary fission reactions. There are two types of atoms present in the reactor at any point of time:
1. An Un-Un-Octium atom which splits into another Un-Bi-Pentium and an Un-Un-Octium atom, every second.
2. An Un-Bi-Pentium atom which splits into an Un-Un-Octium atom every two seconds.
To power the nuclear reactor, initially one Un-Bi-Pentium, one Un-Un-Octium are injected into the reactor by Cisco. The chain reaction continues thereafter.
As the owner of Star Laboratories, Dr. Harrison Wells needs to know the number of atoms which are being produced by the Reactor each second.
Input:
The first line of input contains T, the no. of times Dr. Harrison Wells wants to ask a query. The following T lines contain an integer each, s.
Output:
You need to output T lines where each line denotes the no. of atoms produced in the reactor in each of the sth second. Since the number can be very large, print it modulo 10^9 + 7.
Constraints:
1 <= T <= 1000
1 <= s <= 10000
In the first sample second, only 1 type of each atom is present initially. So in total 2 atoms is the answer.
In the second case, the Un-un-octium splits into one un-un-octium and an un-bi-pentium, resulting in 2 total atoms being produced that second.
