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}\)