ACM-ICPC INC 2009

Problem B

Liar Game

Time Limit: 20s

During the ressurection round 2 of Liar Game, Kanzaki Nao was fooled by Fukunaga Yuuji in a "Light vs. Dark" card game, where Kanzaki Nao chose the "Light" and Fukunaga Yuuji chose "Dark". The game rules is as follows:
Two playing cards are placed inside a bag:
  1. The "Light" card: a regular Joker card with one side printed Joker and a back on the other side.
  2. The "Dark" card: a misprint card that has a back on both sides.
The game consists of multiple rounds, with one round following these steps:
  1. Fukunaga shakes up the bag, and then Kanzaki pulls out a card from the bag.
  2. If the Joker is face-up when pulled out, it is returned to the bag and proceed to the next round (this round is lost). Otherwise the card is flipped over.
  3. If the card is the Joker, the "Light" player gets 1 point, otherwise it must be the misprint card and the "Dark" player gets 1 point.
  4. The card is then returned to the bag and proceed to the next round.
Here we are dealing with a more general "Light vs. Dark" game. Suppose you are Kanzaki Nao who chose "Light" and there are N-1 Fukunaga Yuuji who chose "Dark", which makes the total of N players playing the "Light vs. Dark". Akiyama Shinichi, a mastermind swindler, wants to know the exact probability of Kanzaki Nao getting exactly K points in the game after R rounds.

Input

The first line of input contains an integer T (1 <= T <= 2500), the number of test cases follow.

Each testcase is described in one line consisting 3 integers: N, R, K where 1 <= N,R <= 100,000 and 0 <= K <= R.

Output

For each testcase, output a single line: (P * (2*N)R) mod 1000003, where P is the probability of Kanzaki Nao gets K points (picked the face-down Joker card K times) in a game consisting of R rounds and N players.

Sample InputOutput for Sample Input
6
2 2 1
2 5 2
2 10 5
3 5 1
100 100 14
46624 22965 14070

6
270
61236
3125
975443
408634