Description
Vigilis a master builder with a unique specialization: Dorms. When building a dorm, Vigil always builds it with a width of 2 and a height of n. Vigil also can create an unlimited amount of building materials of any width and height as long as they are integers.
In every contract, Vigil is given a height n and is told to build every variation of the dorm with width 2 and height n ( mirrored and rotated dorms are counted separately if they look different).
Help Vigil calculate how many different dorm variations there are given n.
Input
The first line contains the integer q (1 <= q <= 100).
The following q lines contain the n value, for the height of the tower (1 <= n <= 106).
Output
q lines, each line containing the number of dorm variations mod 109 + 7.