Russian Roulette (Hard)

You went out to celebrate with your $n-1$ friends. You all got drunk and decided that playing Russian roulette with a paintball gun sounds like a great idea.

The gun is a revolver with $c$ chambers ($c \ge n$). Exactly $n-1$ of those chambers contain a paintball, and all others are empty.

The game has one other parameter: a positive integer constant $k$.

At the beginning of the game, all $n$ players stand in a circle. Number the players 0 through $n-1$ in clockwise order. Player 0 takes the gun. The game repeats the following three steps until the gun becomes empty:

1. The person holding the gun shoots themselves. They spin the cylinder to choose one of the chambers uniformly at random, point the gun at themselves, and pull the trigger.
2. If the chosen chamber was empty, exactly $k$ rounds of passing follow. In each round, the holder passes the gun clockwise to the next player still in the game.
3. If the chamber contained a paintball, the player is hit and loses the game. The gun passes clockwise to the next player still in the game, and the hit player leaves the game.

The winner is the only player who is not shot.

For given $n$, $c$, and $k$, compute where you should stand at the beginning to maximize your probability of winning. Also compute the exact value of that probability.

The first line contains an integer $t$, the number of test cases. Each test case is preceded by a blank line.

Each case is a single line with the integers $n$, $c$, and $k$. It is guaranteed that $1 \le k \le n \le c$ and $c \le 1000$.

For each test case, print one line with two space-separated numbers. The first is the position at the beginning of the game that maximizes your probability of winning. The second is a number that encodes the probability of winning from that position.

If several positions are optimal, print the smallest one.

Let the maximum winning probability be the irreducible fraction $p/q$. Print $p \cdot q^{-1} \bmod (10^9+9)$, where $q^{-1}$ is the modular inverse of $q$ modulo $10^9+9$. The maximum probability is guaranteed to be expressible as such a fraction, and the modular inverse of $q$ is guaranteed to exist.

The exact answer for the first test case is $33/65$. Since $65^{-1} \equiv 323076926 \pmod{10^9+9}$, the second number on the first output line is $(33 \times 323076926) \bmod (10^9+9) = 661538468$.