Pawan is going with her girlfriend on date (don't be happy :P concentrate on the question). So he wants to buy some gift for his girlfriend. He just goes to the shop and finds that there are n different gifts in the shop. He has infinite amount of money , so he can buy any number of gifts , but he will buy at least 1 gift for his girlfriend (otherwise she will be angry :P ) and he will never buy all the gifts (otherwise the shop would be empty :P ). Now Pawan wants to know the total number of ways of buying the gifts. Since the answer may be large , print it modulo (10^9 + 7).

Input

First line of input contains t (no. of test cases to follow). Next t lines contains n (number of gifts in the shop).

Output

Print t lines containing the answers for each case modulo (10^9 + 7).

Constraints

1<= t <= 1000
2<= n <= 10^18

Example

Input:
2
2
3

Output:
2
6

Explanation

for 2nd test case , there are 3 gifts in the shop. let those are A,B,C.
Pawan can buy the gifts in following 6 ways - A,B,C,AB,BC,AC.
He cannot buy 0 or all gifts.