PEG Judge - Prime Bag

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 P². 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 P².

Sample Input 1

Sample Output 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 5²=25).

Sample Input 2

Sample Output 2

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)

Tianqi on Jan 27, 2016 - 4:27:27 pm UTC Help

(0/1)

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

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

Bob on Sep 04, 2009 - 11:07:50 pm UTC What is Runtime Error (8: SIGFPE)?

(0/1)

jargon on Sep 05, 2009 - 12:57:13 am UTC Re: What is Runtime Error (8: SIGFPE)?

(2/1)

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

SIG stands for Signal, FPE stands for Floating Point Error. [size=9]Well, I think so...[/size]

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

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

bleung91 on Feb 28, 2009 - 2:38:03 am UTC Alphonse and Beryl

(0/1)

OMG, i still remember where these names came from.

OMG, i still remember where these names came from.

SourSpinach on Feb 28, 2009 - 3:18:20 am UTC Re: Alphonse and Beryl

(0/1)

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.

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.

bleung91 on Feb 28, 2009 - 3:44:31 am UTC Re: Re: Alphonse and Beryl

(1/1)

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 &le; 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.

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.

hansonw1 on Feb 28, 2009 - 3:21:37 am UTC Re: Alphonse and Beryl

(1/1)

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

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

javic on Feb 28, 2009 - 3:59:27 am UTC Re: Alphonse and Beryl

(0/1)

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

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

javic on Feb 28, 2009 - 4:00:21 am UTC Re: Re: Alphonse and Beryl

(2/1)

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

Nice Hanson.. ur solution impressed me.

bbi5291 on Feb 28, 2009 - 2:56:13 pm UTC Re: Re: Re: Alphonse and Beryl

(2/1)

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.

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.