题目描述

小 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 分）：没有任何附加限制。