Prime Bag

Alphonse likes primes. He has a bag filled with P different colorful bouncy balls, where P is a prime and 1 ≤ P ≤ 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 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 mod P2. The answer will fit in a 64-bit signed integer.

Input

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

Output

The output consists of a single line, the number of ways Alphonse can pick the balls mod P2.

Sample Input 1

5

Sample Output 1

1

Explanation 1

Alphonse must leave at least ceil(5/17×5)=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 (mod 52=25).

Sample Input 2

29

Sample Output 2

378

Explanation 2

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

\large$\displaystyle\binom{29}{0}+\binom{29}{1}+\binom{29}{2}+\binom{29}{3}+\binom{29}{4}+\binom{29}{5}+\binom{29}{6}+\binom{29}{7}+\binom{29}{8}+\binom{29}{9}+\binom{29}{10}+\binom{29}{11}+\binom{29}{12}+\binom{29}{13}+\binom{29}{14}+\binom{29}{15}+\binom{29}{16}+\binom{29}{17}+\binom{29}{18}+\binom{29}{19}+\binom{29}{20} = 530596371 \equiv 378 \pmod{29^2}$

All Submissions
Best Solutions


Point Value: 23 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 28, 2009
Author: javic

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Why i am getting all 0s after i change all int to long long


SIGFPE - Division by zero, square root of a negative, etc.

SIG stands for Signal, FPE stands for Floating Point Error. Well, I think so...

OMG, i still remember where these names came from.

Who the devil are Alphonse and Beryl?
Robin Cheng made this problem, I don't see how you could know where he got these names from.

COMC 2007 Part B Question 4:

Alphonse and Beryl are back! They are playing a two person game with the following
rules:

Initially there is a pile of N stones, with N ≤ 2.
- The players alternate turns, with Alphonse going first. On his first
turn, Alphonse must remove at least 1 and at most N − 1 stones from
the pile.
- If a player removes k stones on their turn, then the other player must
remove at least 1 and at most 2k − 1 stones on their next turn.
- The player who removes the last stone wins the game.

et cetera.

They show up on the Waterloo math contests. (Their version of "Alice and Bob", I guess)

yea, mentioning about names, I did take them from COMC, but those are the first names I got from my head xD

Nice Hanson.. ur solution impressed me.applause.gif

hmm. Now that I think of it, we should implement a system like SPOJ, in which the nominal creator of a problem (not necessarily an admin who puts the problem up) has full access to all the problem's submissions, etc.