J. Persian Casino
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Prince of Persia walks into a casino holding the dagger of time...

Initially he has a single gold coin. He goes to a roulette and starts betting. On each bet he chooses between red and black and must bet a positive integer amount of coins on it. If he wins, he gets double his bet back. Otherwise he loses the bet. Roulette outcomes are distributed uniformly (i.e. both red and black have probability of $$$\frac{1}{2}$$$) and independently from each other.

After the roulette outcome is known, Prince may rollback to the point in time immediately before he made the bet and redo it in any way he wants (possibly betting on a different color or betting a different amount of coins). The roulette outcome will not change after doing rollback. Prince wants to make a total of $$$n$$$ bets and he may use the rollback at most $$$m$$$ times throughout them. Rolling back and redoing a bet does not count as making a new bet.

Prince wants to make sure that before each of $$$n$$$ bets he has at least $$$1$$$ coin in his possession to make a valid bet, while otherwise maximizing the expected amount of coins he will leave with. Given $$$n$$$ and $$$m$$$, determine the expected amount of coins Prince would leave with. If it's not possible to guarantee that Prince makes a sequence of $$$n$$$ valid bets, print bankrupt instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of betting rounds Prince will go through and the number of times he is allowed to use the rollback ability of the dagger of time.

The sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if it is not possible to guarantee that Prince makes a sequence of $$$N$$$ valid bets, print bankrupt, otherwise print the expected amount of coins Prince is going to win modulo $$$10^9+9$$$.

Formally, let $$$M = 10^9+9$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Example
Input
4
2 1
4 1
3 2
57639 34614
Output
3
bankrupt
7
869788168
Note

Consider the first test case. According to the rules of the game, he must bet exactly one coin.

  • With probability $$$\frac12$$$, he loses the bet. Since he now has no money but must make another bet, he must rollback and bet the same coin on the opposite color. After this, he has 2 coins and no rollbacks. Suppose he bets 1 coin on his second bet.
    • With probability $$$\frac12$$$, he loses this bet and has no opportunity to rollback. In this scenario, he ends up with 1 coin.
    • With probability $$$\frac12$$$, he wins this bet and again has no opportunity to rollback (e.g. to bet more). He ends up with 3 coins.
  • With probability $$$\frac12$$$, he wins this bet. There is nothing to gain from rolling back. He now has 2 coins and 1 rollback. Suppose he bets 1 coin on his second bet. Whichever way his second bet goes, he now knows the outcome of the roulette roll. Since he has no further bets to make, there is nothing to lose from rolling back. Therefore, he should roll back and bet all his money on the winning color. After that, he ends up with 4 coins.
In total, the expected number of coins Prince of Persia has is $$$\frac14 \cdot 1 + \frac14 \cdot 3 + \frac12 \cdot 4 = 3$$$. It can be shown that this strategy is optimal for the test case.

For the second test case, suppose that Prince of Persia loses the first bet he makes. In that case, he has run out of money, but still has 3 more bets to make. Thus, he is forced to use his only rollback and bet his only coin on the opposite color. Now he has 2 coins. For the remaining three bets, suppose he loses every time. Even if he only bets one coin every time, he will run out of money: he has 2 coins before the second bet, 1 coin before the third bet and no money to make the fourth bet.