Let $p_1, p_2, ..., p_n$ be a permutation of $1,2, ...,n$.

An optimistic permutation follows $p_i > i-2 \, \forall \, i \in [1, n]$.

An over-optimistic permutation has the following properties:

• It is optimistic.
• There exists atleast one $i \,(i \in [1, n])$ such that  $p_i \geq i+2$.

Given $n$, find the count of all over-optimistic permutations modulo $10^9+7$.

Input:

The first line contains $T$ - the number of testcases, followed by T lines each containing one integer $n$.

Output:

For each testcase print the answer on a newline.

Constraints:

• $1 \leq T \leq 500000$
• $1\leq n \leq 10^{18}$