There is a regular convex polygon with n vertices. The vertices are labeled from 0 to n - 1 in a clockwise direction, and each vertex has exactly one monkey. Simultaneously, each monkey moves to a neighboring vertex. A collision happens if at least two monkeys reside on the same vertex after the movement or intersect on an edge. $\\$ Print the number of ways the monkeys can move so that at least one collision happens. Since the answer may be very large, return it modulo $10^9 + 7$.

The first line of input contains $t$, the number of test cases.
Each of the following $t$ lines contains an integer $n$ denoting the number of vertices.

You need to output $t$ lines each containing answer to the corresponding testcase.

($1 \le t \le 2*10^5$)
($3 \le n \le 10^9$)