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
  • Apply
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #253: Tidying up

Project Euler #253: Tidying up

Contest ends in
Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 253 from projecteuler.net

A small child has a “number caterpillar” consisting of forty jigsaw pieces, each with one number on it, which, when connected together in a line, reveal the numbers to in order.

Every night, the child's father has to pick up the pieces of the caterpillar that have been scattered across the play room. He picks up the pieces at random and places them in the correct order.
As the caterpillar is built up in this way, it forms distinct segments that gradually merge together.
The number of segments starts at zero (no pieces placed), generally increases up to about eleven or twelve, then tends to drop again before finishing at a single segment (all pieces placed).

For example:

image

Let be the maximum number of segments encountered during a random tidy-up of the caterpillar.
For a caterpillar of ten pieces, the number of possibilities for each is

image

so the most likely value of is and the average value is , rounded to six decimal places.

Given the -piece caterpillar, what is the average value of ? Give your answer modulo . As the average value of is obviously rational and could be represented as , print .

Input Format

The first line of each test file contains exactly two numbers separated by a single space, and .

Constraints

  • is prime.

Output Format

Print exactly one number: the average value of modulo .

Sample Input 0

1 1000000007

Sample Output 0

1

Explanation 0

The only valid permutation allows only one segment of length .

Sample Input 1

10 1000000009

Sample Output 1

283712528

Explanation 1

Author

bayleef

Difficulty

Medium

Max Score

100

Submitted By

443

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

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