We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. HourRank 21
  3. Sam's Numbers

Sam's Numbers

Problem
Submissions
Leaderboard
Discussions
Editorial

Once, Sam started to write down numbers in a row. Let's call this list .

Each number was between and , inclusive, and the absolute difference between any adjacent pair of numbers was at most , i.e., for all . As soon as she stopped writing, she noticed that the sum of the numbers she wrote was .

For example, if , and , then she could have written the list . Notice that each number is between and , inclusive, the absolute difference between any adjacent pair is , and the sum is .

image

She then started thinking how many different ways this could have happened, i.e., how many lists of numbers satisfy all the conditions above. Can you help her in calculating this number?

As the answer can be very large, apply a modulo on the result before printing it.

Input Format

The first and only line of input contains three space-separated integers denoting , and respectively.

Constraints

Subtasks

  • For of the maximum score,
  • For of the maximum score,

Output Format

Print a single line containing a single integer denoting the requested number modulo .

Sample Input 0

4 3 1

Sample Output 0

5

Explanation 0

There are such lists:

  1. ]

Notice that

  • The sum of the numbers in each list is .
  • Each value is between and , inclusive.
  • The absolute difference between any two adjacent pairs is .

Author

nikasvanidze

Difficulty

Medium

Max Score

50

Submitted By

783

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download all test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy