[RC-03] 随机树生成器

小 R 有一个随机树生成器，其工作原理如下： - 输入 $n$，则对于每个 $1<i\le n$，随机选择一个 $[1,i)$ 中的节点作为其父亲。返回这棵树。 给定 $n,k$，小 R 想知道可能生成的所有 $n$ 个点的树中，$k$ 号点的度数和。 由于答案可能很大，请输出答案模 $10^9+9$ 的值。

**本题有多组数据。** 第一行一个整数，是数据组数 $T$。 接下来 $T$ 行，每行两个正整数 $n,k$。

$T$ 行，每行一个整数，为这组数据的答案模 $10^9+9$ 的值。

3
3 1
3 2
3 3

3
3
2

【样例说明】 - 数据 $1$：一共有两种情况，$1$ 号点的度数分别为 $1,2$。因此答案为 $3$。 - 数据 $2$：一共有两种情况，$2$ 号点的度数分别为 $1,2$。因此答案为 $3$。 - 数据 $3$：一共有两种情况，$3$ 号点的度数均为 $1$。因此答案为 $2$。 【数据范围】 本题捆绑测试。 对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le k\le n\le 10^7$。详细数据范围如下。 - Subtask 1（20 分）：$T\le 50$，$n\le 8$。 - Subtask 2（55 分）：$T=1$，$n\le 10^5$。 - Subtask 3（20 分）：$T=1$。 - Subtask 4（5 分）：没有任何附加限制。