The link to the Russian translation.

Alex has opened the evil vault and is looking for her sister. The vault is evil and has an unstable shape. All Alex knows about it is this:

There are n spots in the vault and there are tunnels between some pairs of spots. The graph of these spots is simple, undirected and connected.

In an undirected graph, the distance between v and u (d(v,u)) is the length (number of edges) of the shortest path from v to u. Diameter of a graph is the value of max(d(v, u) for v, u in V (set of vertices)).

Alex also knows that if she adds any edge that doesn't exist in the current graph (edge between to distinct vertices) its diameter will change.

Alex wants to know the number of graphs with this property. She also notes that the order (label) of vertices doesn't matter (so she wants the number of isomorphism classes of such graphs).

Alex has a great position in the armory, so, don't make her force you...!

Input

The first line of input contains a single integer T, the number of scenarios (1 ≤ T ≤ 500). The next T lines contain the description of these scenarios, each with one integer n (1 ≤ n ≤ 10⁶).

Output

For each scenario prints its answer modulo 1000 000 007 (10⁹+7) in one line.