라이어 게임

라이어 게임 부활 라운드 2에서, 칸자키 나오는 후쿠나가 유지에게 "빛과 어둠" 카드 게임에서 속아 넘어갔다. 칸자키 나오는 "빛"을, 후쿠나가 유지는 "어둠"을 선택했다. 게임 규칙은 다음과 같다.

주머니 안에 카드 두 장이 들어 있다.

1. "빛" 카드: 한 면에 조커가 인쇄되어 있고 다른 면에 뒷면이 있는 보통 조커 카드.
2. "어둠" 카드: 양면이 모두 뒷면인 오인쇄 카드.

게임은 여러 라운드로 구성되며, 한 라운드는 다음과 같다.

1. 후쿠나가가 주머니를 흔든 뒤, 칸자키가 주머니에서 카드 한 장을 꺼낸다.
2. 꺼낸 카드가 앞면이 조커면 주머니에 다시 넣고 다음 라운드로 넘어간다(이 라운드는 진 것이다). 그렇지 않으면 카드를 뒤집는다.
3. 카드가 조커면 "빛" 플레이어가 1점을 얻고, 그렇지 않으면 오인쇄 카드이므로 "어둠" 플레이어가 1점을 얻는다.
4. 카드를 주머니에 다시 넣고 다음 라운드로 넘어간다.

여기서는 더 일반화된 "빛과 어둠" 게임을 다룬다. 주머니에 N장의 카드가 있다고 하자. 그중 한 장이 "빛" 카드이고, 나머지 카드는 모두 "어둠" 카드이다. 사기꾼 아키야마 신이치는 R라운드 후 칸자키 나오가 정확히 K점을 얻을 확률을 정확히 알고 싶어 한다.

첫 줄에는 정수 T (1 <= T <= 2500)가 주어지며, 그 뒤에 T개의 테스트 케이스가 따른다.

각 테스트 케이스는 한 줄에 3개의 정수 N, R, K로 주어진다. 여기서 1 <= N, R <= 100,000이고 0 <= K <= R이다.

각 테스트 케이스마다 한 줄에 (P * (2*N)R) mod 1000003을 출력한다. 여기서 P는 N장의 카드로 R라운드를 진행하는 게임에서 칸자키 나오가 K점을 얻을 확률(뒷면 조커 카드를 K번 뽑을 확률)이다.