波斯王子带着时间匕首走进了一家赌场……

起初他有一枚金币。他来到轮盘赌桌前开始下注。每一轮他都要在红色和黑色之间做出选择，并且必须押上正整数枚金币。如果他赢了，他会拿回双倍的筹码。否则，他将输掉这笔赌注。轮盘赌的结果分布均匀（即红色和黑色出现的概率均为 $\frac{1}{2}$），且各轮结果相互独立。

在轮盘赌结果揭晓后，王子可以选择回溯到下注前的那一刻，并以他想要的任何方式重新下注（可能押注不同的颜色或不同的金币数量）。回溯后，轮盘赌的结果不会改变。王子想要进行总共 $n$ 轮下注，并且在整个过程中最多可以使用 $m$ 次回溯。回溯并重新下注不计作新的下注轮次。

王子希望确保在进行 $n$ 轮下注中的每一轮之前，他手中至少有 1 枚金币以进行有效的下注，同时在此前提下最大化他最终剩余金币的期望值。给定 $n$ 和 $m$，确定王子最终剩余金币的期望值。如果无法保证王子能完成 $n$ 轮有效下注，则输出 bankrupt。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示王子将要进行的下注轮数以及他被允许使用回溯能力的次数。

所有测试用例的 $m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，如果无法保证王子能完成 $n$ 轮有效下注，输出 bankrupt；否则，输出王子最终获胜金币数量的期望值，对 $10^9 + 9$ 取模。

形式化地，令 $M = 10^9 + 9$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数且 $q \not\equiv 0 \pmod M$。输出等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，输出一个满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$ 的整数 $x$。

样例

输入 1

4
2 1
4 1
3 2
57639 34614

输出 1

3
bankrupt
7
869788168

说明

考虑第一个测试用例。根据游戏规则，他必须恰好押注一枚金币。

• 有 $\frac{1}{2}$ 的概率，他输掉了赌注。由于他现在没有钱但必须进行下一轮下注，他必须回溯并将同一枚金币押在相反的颜色上。之后，他拥有 2 枚金币且没有回溯机会。假设他在第二轮下注中押了 1 枚金币：
  • 有 $\frac{1}{2}$ 的概率，他输掉了这轮赌注且没有回溯机会。在这种情况下，他最终剩下 1 枚金币。
  • 有 $\frac{1}{2}$ 的概率，他赢得了这轮赌注且没有回溯机会（例如无法再下注更多）。他最终剩下 3 枚金币。
• 有 $\frac{1}{2}$ 的概率，他赢得了这轮赌注。此时回溯没有任何收益。他现在有 2 枚金币和 1 次回溯机会。假设他在第二轮下注中押了 1 枚金币。无论第二轮下注结果如何，他现在都知道了轮盘赌的结果。由于没有后续的下注轮次，回溯没有任何损失。因此，他应该回溯并将他所有的钱押在获胜的颜色上。之后，他最终剩下 4 枚金币。

总的来说，波斯王子剩余金币的期望值为 $\frac{1}{4} \cdot 1 + \frac{1}{4} \cdot 3 + \frac{1}{2} \cdot 4 = 3$。可以证明该策略对于此测试用例是最优的。

对于第二个测试用例，假设波斯王子输掉了他进行的第一轮下注。在这种情况下，他的钱用光了，但还有 3 轮下注要进行。因此，他被迫使用他唯一的 1 次回溯机会，并将他仅剩的 1 枚金币押在相反的颜色上。现在他有 2 枚金币。对于剩下的三轮，假设他每次都输。即使他每次只押 1 枚金币，他的钱也会用光：他在第二轮下注前有 2 枚金币，第三轮下注前有 1 枚金币，而第四轮下注时已没有钱。