|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||19||9||8||44.444%|
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:
The game consists of multiple rounds, with one round following these steps:
- The "Light" card: a regular Joker card with one side printed Joker and a back on the other side.
- The "Dark" card: a misprint card that has a back on both sides.
- Fukunaga shakes up the bag, and then Kanzaki pulls out a card from the bag.
- 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.
- 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.
- 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: N, R, K 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.
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