## 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*

^{2}. 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*

^{2}.

### 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 5

^{2}=25).

### Sample Input 2

29

### Sample Output 2

378

### Explanation 2

Th number of ways to pick these balls is equal to:
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)

Tianqion Jan 27, 2016 - 4:27:27 pm UTC HelpBobon Sep 04, 2009 - 11:07:50 pm UTC What is Runtime Error (8: SIGFPE)?jargonon Sep 05, 2009 - 12:57:13 am UTC Re: What is Runtime Error (8: SIGFPE)?SIG stands for Signal, FPE stands for Floating Point Error. Well, I think so...

bleung91on Feb 28, 2009 - 2:38:03 am UTC Alphonse and BerylSourSpinachon Feb 28, 2009 - 3:18:20 am UTC Re: Alphonse and BerylRobin Cheng made this problem, I don't see how you could know where he got these names from.

bleung91on Feb 28, 2009 - 3:44:31 am UTC Re: Re: Alphonse and BerylAlphonse 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.

hansonw1on Feb 28, 2009 - 3:21:37 am UTC Re: Alphonse and Beryljavicon Feb 28, 2009 - 3:59:27 am UTC Re: Alphonse and Beryljavicon Feb 28, 2009 - 4:00:21 am UTC Re: Re: Alphonse and Berylbbi5291on Feb 28, 2009 - 2:56:13 pm UTC Re: Re: Re: Alphonse and Beryl