러시안 룰렛 (어려움)

여러분은 $n-1$명의 친구와 함께 축하하러 나갔다. 모두 술에 취했고, 페인트볼 권총으로 러시안 룰렛을 하자는 생각이 좋다고 결정했다.

권총은 약실이 $c$개인 리볼버다($c \ge n$). 정확히 $n-1$개의 약실에는 페인트볼이 들어 있고, 나머지 약실은 모두 비어 있다.

게임에는 양의 정수 상수 $k$가 하나 더 있다.

게임 시작 시 $n$명의 플레이어가 원형으로 선다. 시계 방향으로 0번부터 $n-1$번까지 번호를 매긴다. 0번 플레이어가 권총을 든다. 권총이 빌 때까지 다음 세 단계를 반복한다.

1. 권총을 든 사람이 자기 자신에게 쏜다. 약실을 무작위로 균일하게 돌려 하나를 고른 뒤, 권총을 자신에게 겨누고 방아쇠를 당긴다.
2. 고른 약실이 비어 있었다면, 정확히 $k$번 권총을 넘기는 라운드가 진행된다. 각 라운드에서 권총을 든 사람은 시계 방향으로, 아직 게임에 남은 다음 사람에게 권총을 넘긴다.
3. 약실에 페인트볼이 들어 있었다면 그 사람은 맞고 게임에서 진다. 이때도 권총은 시계 방향으로 아직 남은 다음 사람에게 넘어가고, 맞은 사람은 게임에서 빠진다.

승자는 총에 맞지 않은 유일한 사람이다.

$n$, $c$, $k$가 주어졌을 때, 승률을 최대로 하려면 게임 시작 시 어디에 서야 하는지 구하라. 또한 그 위치에서의 승률의 정확한 값도 구하라.

첫 줄에 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 케이스는 정수 $n$, $c$, $k$가 한 줄에 주어진다. $1 \le k \le n \le c$이고 $c \le 1000$이다.

각 테스트 케이스마다 공백으로 구분된 두 수를 한 줄에 출력한다. 첫 번째 수는 승률을 최대로 하는 게임 시작 위치이고, 두 번째 수는 그 위치에서의 승률을 나타내는 값이다.

최적의 위치가 여럿이면 가장 작은 위치를 출력한다.

최대 승률을 기약분수 $p/q$라 하자. $10^9+9$를 법으로 한 $q$의 역원을 $q^{-1}$이라 할 때, $p \cdot q^{-1} \bmod (10^9+9)$를 출력한다. 최대 확률은 이런 분수로 표현할 수 있고, $q$의 모듈러 역원이 존재함이 보장된다.

첫 번째 테스트 케이스의 정확한 답은 $33/65$다. $65^{-1} \equiv 323076926 \pmod{10^9+9}$이므로, 출력 첫 줄의 두 번째 수는 $(33 \times 323076926) \bmod (10^9+9) = 661538468$이다.