Problem Description
A carousel has C number of seats, all lined up in a circular fashion around the centre of the carousel.
A school principal wants to rewards it's students to a carousel ride. The school has N pupils in total and the principal has booked the carousel for 1 ride, thus being able to allow C students to enjoy the carousel ride experience.
How many different ways can the school principal select students for the ride? 2 ways are considered different if either the students selected for the carousel ride are different, or the seating positions of the students are different.
For the following examples, you may assume that C = 4 and N = 5, and the students are labelled from 1 to 5.
Carousel:
5
4 3
2
and
Carousel:
4
2 5
3
are considered only as 1 way, since both reads 5324 if you start from student 5 and read clockwise. [It is just the same thing but rotated into a different angle]
However,
Carousel:
5
4 2
3
and
Carousel:
5
4 3
2
would be considered as 2 distinct different ways.
For clarity,
Carousel:
5
4 2
3
and
Carousel:
1
4 2
3
will be considered as 2 distinct different ways as well since the students selected for the carousel are different.
Input
The input will consist of 2 integers, N followed by C. N will be in between 1 and 1000000 inclusive while C will be in between 1 and N inclusive.
Output
Since the number can be very large, please output the remainer of the actual answer when divided by 1000003. (mod 1000003).
Note
For this question, you are supposed to input from 'carousel.in', and output to 'carousel.out'.
Sample Input 1
5 4
Sample Output 1
30
Sample Input 2
4 2
Sample Output 2
6
Sample Input 3
13 13
Sample Output 3
163
Explanation for Output 3
The total number of ways is 479001600.