체스

바이트맨은 정확히 오후 5시에 바이트가이의 집 문을 두드립니다. 사실 그럴 필요도 없었습니다. 바이트가이는 친구가 얼마나 시간을 잘 지키는지 알고 있었기에 이미 문을 열려던 참이었으니까요.

따뜻한 차를 한 잔 마신 뒤, 바이트가이는 미리 약속한 대로 체스를 두려고 체스판을 가져옵니다. 하지만 바이트맨은 완전 정보 게임은 충분히 도전적이지 않다며 다른 것을 해 보자고 제안합니다. 마땅히 반박할 말을 찾지 못한 바이트가이는 그 말에 동의합니다. 한 번도 시도해 본 적 없는 지적인 도전을 찾는 데에는 시간이 조금 걸렸지만, 두 친구는 결국 다음 문제를 풀기로 합니다.

$n \times n$ 크기의 체스판이 주어집니다. 이 판 위에 룩 $n$개를 놓되, 각 행과 각 열에 룩이 최대 한 개만 있도록 하는 경우의 수를 구하세요. 단, 체스판을 같은 평면 안에서 90° 회전시켰을 때 룩의 배치가 정확히 똑같이 보여야 합니다.

회전 후 칸의 색깔은 달라질 수 있지만, 이 문제에서는 색깔을 고려하지 않습니다.

입력의 유일한 줄에 정수 $n$ ($1 \le n \le 50000$) 하나가 주어집니다.

각 행과 각 열에 룩이 최대 한 개만 있고 90° 회전에도 배치가 바뀌지 않는, $n \times n$ 판 위 룩 $n$개의 배치의 수를 정수 하나로 출력하세요.