P17436 "LWLV Round 1" Jump!

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

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$.**

**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$.

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

#### Sample Explanation When $n=2$, there are the following $3$ sequences $a$ that satisfy the requirement: $$[1,1]$$ $$[2,1]$$ $$[2,2]$$ #### Constraints |Subtask ID|$T\le$|$n\le$|Score| |:-:|:-:|:-:|:-:| |$0$|$8$|$8$|$5$| |$1$|$5$|$1000$|$20$| |$2$|$5$|$10^5$|$25$| |$3$|$5\times 10^4$|$10^{18}$|$50$| For $100\%$ of the testdata, it is guaranteed that $T\le 5\times 10^4$ and $n\le 10^{18}$. Translated by ChatGPT 5