Prime BagAlphonse 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.
InputThe input consists of a single line, the integer P ≤ 10,000,000. You may assume that P is always a prime.
OutputThe output consists of a single line, the number of ways Alphonse can pick the balls mod P2.
Sample Input 1
Sample Output 1
Explanation 1Alphonse 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
Sample Output 2
Explanation 2Th number of ways to pick these balls is equal to:
Point Value: 23 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 28, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3