A town had a huge temple. The temple was world wide famous. People from all over the world would come to the temple to visit it. This temple had a very huge number of visiters. Lets say the number of visitors of the temple would be n. The priest would distribute sweets to the visitors. However he followed a certain pattern in the distribution of sweets. Since it was such a huge queue of visitors, the priest would be distributing more number of sweets to those who stood far in the queue. Suppose lets take the arrangement of people in the queue in such a way that the people are standing along the x-axis in the consecutive integral points. That is person 1 is standing at the coordinate (1,0), person 2 is standing at the coordinate (2,0) and so on. The pattern of distribution of sweets that the priest follows is such that

1.first and second person will always receive only one sweet

2.For the person who is standing at the coordinate greater than 2 the person will receive the sweets equal to the sweets received by previous person plus twice the sweets received by the person standing at two positions earlier than him.

One day the media person comes and asks priests how many sweets would a particular person receive if he is standing at that position. Since priest is a bit weak in maths help him to asnwer the queries of media person. Since answer might be very large print it modulo 1000000007.

Input:

First line contains the number of test cases (1<=T<=10^5)

Next T lines contains the queries the value of n .(1<=n<=10*10^9).

Output:

Answer how many number of sweets the nth person would be getting.