Liar Game

During resurrection round 2 of Liar Game, Kanzaki Nao was fooled by Fukunaga Yuuji in a "Light vs. Dark" card game, where Kanzaki Nao chose "Light" and Fukunaga Yuuji chose "Dark". The rules of the game are as follows:

Two playing cards are placed inside a bag:

1. The "Light" card: a regular Joker card with Joker printed on one side 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, and one round proceeds as follows:

1. Fukunaga shakes 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 the game proceeds 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 returned to the bag and the game proceeds to the next round.

Here we deal with a more general "Light vs. Dark" game. Suppose there are N cards in the bag. One of them is the "Light" card, and all of the other cards are "Dark" cards. Akiyama Shinichi, a mastermind swindler, wants to know the exact probability that Kanzaki Nao gets exactly K points in the game after R rounds.

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

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

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