Background

Little L really loves to jump, but this also makes him get faked out and knocked away in basketball games.

Problem Description

Little L has a sequence $a$ of length $n$, where all elements are within $[1,n]$.

Little L has a variable $x$, initially $x=1$.

Then Little L will perform the jump operation on the variable several times until no more operations can be performed. Specifically, if $1\le x\le n$, then $x$ increases by $a_x$.

Due to the nature of the jump operation, in the end we will have $n< x\le 2\times n$. He wants to know how many sequences $a$ make $x=n+1$ after performing the jump operation several times.

Since the answer may be very large, output the result modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, denoting the number of test cases.

Then there are $T$ test cases. For each test case, one line contains a positive integer $n$.

Output Format

For each test case, output the answer modulo $10^9+7$.

3
2
20
1145141919810

3
292439931
825800492

Hint

Sample Explanation

When $n=2$, there are the following $3$ sequences $a$ that satisfy the requirement:

Constraints

For $100\%$ of the testdata, it is guaranteed that $T\le 5\times 10^4$ and $n\le 10^{18}$.

Translated by ChatGPT 5