Alphonse likes primes. He has a bag filled with $P$ different colorful bouncy balls, where $P$ is a prime and $1\le P\le 10000000$. 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 $mod{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 10000000$. 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 $mod{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(\mathrm{mod}{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 (\genfrac{}{}{0ex}{}{29}{0})+(\genfrac{}{}{0ex}{}{29}{1})+\cdots +(\genfrac{}{}{0ex}{}{29}{20})=530596371\equiv 378(\mathrm{mod}{29}^2)}$$