P6862 [RC-03] Random Tree Generator

Little R has a random tree generator. It works as follows: - Input $n$. Then for each $1

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

Output $T$ lines. Each line contains one integer: the answer for that test case modulo $10^9+9$.

[Sample Explanation] - Testdata $1$: There are two cases, where the degree of node $1$ is $1$ and $2$. Therefore the answer is $3$. - Testdata $2$: There are two cases, where the degree of node $2$ is $1$ and $2$. Therefore the answer is $3$. - Testdata $3$: There are two cases, where the degree of node $3$ is always $1$. Therefore the answer is $2$. [Constraints] This problem uses bundled testdata. For $100\%$ of the testdata, $1\le T\le 10^5$, $1\le k\le n\le 10^7$. The detailed constraints are as follows. - Subtask 1 (20 points): $T\le 50$, $n\le 8$. - Subtask 2 (55 points): $T=1$, $n\le 10^5$. - Subtask 3 (20 points): $T=1$. - Subtask 4 (5 points): No additional constraints. Translated by ChatGPT 5