시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB38251657.143%

## 문제

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 there are N cards in the bag. One of them is the "Light" card, and all of the other cards are the "Dark" cards. Akiyama Shinichi, a mastermind swindler, wants to know the exact probability of Kanzaki Nao getting 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 follow.

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

## 출력

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 cards.

## 예제 입력 1

6
2 2 1
2 5 2
2 10 5
3 5 1
100 100 14
46624 22965 14070


## 예제 출력 1

6
270
61236
3125
975443
408634


## 출처

• 문제의 잘못된 점을 전체적으로 찾은 사람: jh05013