The problem statement is very, easy just compute the value of x given the value of n.

Input

The first line will contains T the number of test cases, the following T lines will contain the value of n.

1 <= T <= 10^5

1 <= n < 10^7

Output

For every n print the value of x % (10^9 + 7).

Example

Input:
5
1
5
10
15
33

Output:
1
80
5120
245760
733919781