P8432 "WHOI-2" ぽかぽかの星

 You are drinking hot cocoa in a snow cave while counting stars. But this time, the stars are replaced by sequences. Clever as you are, you can surely count the sequences clearly.

How many non-decreasing **positive integer** sequences $a_i$ of length $n$ satisfy: - $0 < a_1 \le a_2 \le a_3 \dots \le a_n \le k$. - $\forall i \ne j, a_i + a_j \ne k + 1$. Output the answer modulo $10^9 + 7$.

**This problem has multiple test cases.** The first line contains a positive integer $T$. The next $T$ lines each contain two positive integers $n, k$.

Output $T$ lines, each containing one positive integer, the answer.

**This problem uses bundled testdata.** - $\text{subtask1(20pts)}: T = 5, 1 \le n, k \le 5$. - $\text{subtask2(80pts)}:$ No special constraints. For $100\%$ of the testdata, $T \le 100$, $1 \le n, k \le 5 \times 10^6$, and $1 \le \sum n, \sum k \le 6 \times 10^7$. Translated by ChatGPT 5