Description

Little R has a random tree generator. It works as follows:

• Input $n$. Then for each $1<i\le n$, randomly choose a node in $[1,i)$ as its parent. Output the resulting tree.

Given $n,k$, Little R wants to know, among all possible trees with $n$ nodes that can be generated, the sum of the degrees of node $k$.

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

Input Format

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 Format

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

3
3 1
3 2
3 3

3
3
2

Hint

[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