oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

carousel Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

carousel.html

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.

Tags

Ad Hoc, Number Theory, ToFixStatement

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
120101s64MBMinimum
230101s64MBMinimum
350101s64MBMinimum
4031s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o carousel -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.