Chess

Time limit2sMemory limit512 MB

Summary

An n by n board with n rooks, at most one per row and column, and the placement unchanged after a 90 degree rotation is given. Count the number of such placements for n up to 50000.

Level: Medium6 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

Byteman knocks on Byteguy's door at exactly 5 pm. This is not really necessary: Byteguy knows his friend's punctuality well and is already reaching for the handle.

After a cup of warm tea, Byteguy brings out a chessboard for the game they had planned. Byteman objects that perfect-information games are not challenging enough and suggests something more interesting. Byteguy cannot find a good counter-argument, so the two friends look for a fresh intellectual challenge and eventually agree on the following problem.

You are given an $n \times n$ chessboard. Count the number of ways to place $n$ rooks on it so that every row and every column contains at most one rook, and the whole arrangement looks exactly the same after the board is rotated by 90° in its own plane.

The colours of the squares may change under the rotation, but that does not matter here.

Input

The only line of input contains a single integer $n$ ( $1 \le n \le 50000$ ).

Output

Print a single integer: the number of arrangements of $n$ rooks on the $n \times n$ board such that each row and each column holds at most one rook and the arrangement is unchanged by a 90° rotation.

Examples4

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
0
```
Example 3
Input
```
4
```
Expected output
```
2
```
Example 4
Input
```
5
```
Expected output
```
2
```