P9035 "KDOI-04" Pont des souvenirs

Although this is a C, it still is. 

Given positive integers $n, k$, find how many positive integer sequences $a$ of length $n$ satisfy: * $0 < a_1 \le a_2 \le a_3 \le \cdots \le a_n \le k$; * $\forall\ i \not= j$, $a_i + a_j \le k + 1$. Output the answer modulo $10^9 + 7$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case, the input contains one line with two positive integers $n, k$.

For each test case, output one line with one integer, representing the answer.

**[Sample Explanation]** For the $1$st test case, all sequences that satisfy the requirements are $(1, 1)$ and $(1, 2)$. For the $2$nd test case, all sequences that satisfy the requirements are $(1)$, $(2)$, and $(3)$. **[Constraints]** For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 2 \times 10^5$, $1 \le n, k \le 10^7$. **This problem uses bundled test cases.** |Subtask ID|Points|$T \le$|$n \le$|$k$| |:-:|:-:|:-:|:-:|:-:| |$1$|$8$|$5$|$5$|$\le 5$| |$2$|$3$|$10^5$|$10^7$|$= 1$| |$3$|$3$|$10^5$|$10^7$|$= 2$| |$4$|$8$|$10^5$|$10^7$|$= 3$| |$5$|$16$|$10$|$200$|$\le 200$| |$6$|$16$|$10$|$3000$|$\le 3000$| |$7$|$8$|$10^4$|$10^7$|$\le 5$| |$8$|$8$|$100$|$10^7$|$\le 10^5$| |$9$|$30$|$2 \times 10^5$|$10^7$|$\le 10^7$| Translated by ChatGPT 5