There are n ballons of different colors. killjee hates balloons and want to blast all of them but he can't as he is too lazy so he decided to blow odd number of balloons. He wants to know in how many ways he can select odd number of balloons to blast them.

As you all know killjee is too weak in maths please help him moreover killjee is so lazy that he wants the result modulo \(10^7+7\).

** Input **

First line of input contains a single integer t denoting number of test cases

each test case has a single integer n as input

** Note **

Please use fast i/o i.e. scanf/printf in c++

Output

Print the answer of each test case in separate lines

Constraints

\( t \le 5*10^6\)

\( n \le 10^{18}\)