[An easier version of this problem was used in the Argentinian Programming Tournament of 2013. You may want to try it before proceeding with this one: http://www.spoj.com/problems/TAP2013J/ ]

Jaimito loves to play with the N identical stones that he was given for his birthday, piling them to form mountains of various sizes. His happiness would be perfect if her mother, Jimena, did not constantly remind him that at the end of the day comes the Time to Arrange the Piles (TAP). It is then that Jaimito must destroy his mountains of stones, which he had piled up with so much effort.

Because Jimena knows how much Jaimito is bothered by the TAP, she suggests to play a game with him in order to make this task more fun. Jaimito and his mother take turns to play, with Jaimito starting because he is the youngest. Initially there are one or more mountains, each one of them composed of a certain number of stones. In his turn each player chooses a mountain with more than one stone and divides it to form two mountains, not necessarily of the same size. The game continues in this way until one of the players cannot make a valid move, at which point this player is declared the looser, the other player being the winner.

Jaimito is a very smart kid, and he has realized that he can distribute the N stones to form the mountains in a strategic way, so as to be certain that when they begin to play with these mountains he will undoubtedly win during the TAP. Because of the way the game works, Jaimito will not consider that two initial arrangements of the stones are different if they only change in the order in which the mountains are given. This means that in order for him to consider two initial distributions to be different, these need to have a different number of mountains or, if the number of mountains is the same, then the stones must be distributed in a different way among the mountains. For example, if Jaimito has N = 4 stones, there are five ways in which he can initially distribute them in mountains: four mountains of one stone each; two mountains of one stone each, and another mountain with two stones; one mountain of one stone, and another mountain with three stones; two mountains of two stones each; and, lastly, a single mountain with all four stones.

Because Jaimito does not want his mother to realize that he is cheating, he wants to change the initial distribution of the N stones every day. He is convinced that there are many different ways to initially arrange the stones that will guarantee him the victory, but he does not know how many exactly. For example, in the case with N = 4 stones Jaimito only has two possible ways to choose from: a single mountain with four stones, or two mountains of one stone each and another mountain with two stones. Your team's task in this problem is to help Jaimito count the number of different ways in which he can distribute his N stones in mountains in such a way that his victory is certain when playing against Jimena. In this way, Jaimito will rest assured knowing how many days he can win without his mother doubting of his good intentions.

Input

The first line contains an integer number T, the number of test cases (1 ≤ T ≤ 10⁴). Each of the following T lines contains an integer number N, representing the number of stones Jaimito has (2 ≤ N ≤ 10⁵).

Output

For each test case print a line containing a single integer number representing the number of different ways in which the N stones can initially be arranged in mountains so as to guarantee that Jaimito will win the game against Jimena. Because the answer can be a very large number, you only have to print the remainder of its division by 10⁹+7.

Example

Input:
2
4
12345

Output:
2
483042273