## Prime Bag

View as PDF

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

Problem type

Alphonse likes primes. He has a bag filled with different colorful bouncy balls, where is a prime and . 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 of all the balls to Beryl (If this is not an integer, round it up). Note that and 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 balls, just to be really nice to Beryl.

Since this number may be ridiculously large, output the answer . The answer will fit in a -bit signed integer.

#### Input Specification

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

#### Output Specification

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

#### Sample Input 1

5

#### Sample Output 1

1

#### Explanation 1

Alphonse must leave at least balls to Beryl. Therefore he may take or balls. Taking balls can be done in way, ball in ways, balls in ways, and balls in ways.
In total there are ways to pick those balls, so the answer is .

#### Sample Input 2

29

#### Sample Output 2

378

#### Explanation 2

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