Alphonse likes primes. He has a bag filled with ~P~ different colorful bouncy balls, where ~P~ is a prime and ~1 \le P \le 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 ~\frac{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 ~\bmod P^2~. The answer will fit in a ~64~-bit signed integer.

Input Specification

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

Output Specification

The output consists of a single line, the number of ways Alphonse can pick the balls ~\bmod P^2~.

Sample Input 1

5

Sample Output 1

1

Explanation 1

Alphonse must leave at least ~\lceil \frac{5}{17} \times 5 \rceil = 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 \pmod{5^2 = 25}~.

Sample Input 2

29

Sample Output 2

378

Explanation 2

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

$$\displaystyle \binom{29}{0}+\binom{29}{1}+\dots+\binom{29}{20} = 530\,596\,371 \equiv 378 \pmod{29^2}$$