Prime Bag

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

Alphonse likes primes. He has a bag filled with P different colorful bouncy balls, where P is a prime and 1 \le P \le 10\,000\,000. He wants to pick a number of balls out of the bag to keep for himself, but he has a good friend Beryl, to whom he will give the rest of the balls, and Alphonse does not want to be mean, so he decides that he will leave at least \frac{5}{17} of all the balls to Beryl (If this is not an integer, round it up). Note that 5 and 17 are also primes that Alphonse likes.

Alphonse would like to find out how many different ways he can pick the balls. Note that Alphonse may also pick 0 balls, just to be really nice to Beryl.

Since this number may be ridiculously large, output the answer \bmod P^2. The answer will fit in a 64-bit signed integer.

Input Specification

The input consists of a single line, the integer P \le 10\,000\,000. You may assume that P is always a prime.

Output Specification

The output consists of a single line, the number of ways Alphonse can pick the balls \bmod P^2.

Sample Input 1


Sample Output 1


Explanation 1

Alphonse must leave at least \lceil \frac{5}{17} \times 5 \rceil = 2 balls to Beryl. Therefore he may take 0, 1, 2, or 3 balls. Taking 0 balls can be done in 1 way, 1 ball in 5 ways, 2 balls in 10 ways, and 3 balls in 10 ways.
In total there are 26 ways to pick those balls, so the answer is 1 \pmod{5^2 = 25}.

Sample Input 2


Sample Output 2


Explanation 2

The number of ways to pick these balls is equal to:

\displaystyle \binom{29}{0}+\binom{29}{1}+\dots+\binom{29}{20} = 530\,596\,371 \equiv 378 \pmod{29^2}


There are no comments at the moment.