Checker Challenge timer 1초 memory 128MB

6*6체커보드에서 6개의 체커들은 아래 그림과 같이 배치될 수 있다.

각 체커는 한 행에 1개, 한 열에 1개씩 밖에 배치할 수 없다.

두 대각선(기울기 증가, 기울기 감소)에도 한 개의 체커만 둘 수 있다.

이 조건을 만족하면서 배치한 그림이 다음 그림이다.

          Column

    1   2   3   4   5   6

  -------------------------

1 |   | O |   |   |   |   |

  -------------------------

2 |   |   |   | O |   |   |

  -------------------------

3 |   |   |   |   |   | O |

  -------------------------

4 | O |   |   |   |   |   |

  -------------------------

5 |   |   | O |   |   |   |

  -------------------------

6 |   |   |   |   | O |   |

  -------------------------​ 

결과는 아래와 같이 각 행에 대응하는 열의 위치로 나타낼 수 있다.

행 : 1 2 3 4 5 6

열 : 2 4 6 1 3 5

위 예는 체커보드에서 구할 수 있는 결과의 한 예이다.

결과는 행은 1~6으로 고정하고 이에 대한 열을 의미한 2 4 6 1 3 5를 하나의 결과라고 부른다.

체커판의 크기 N이 주어질 때, 모든 결과의 수를 구하는 프로그램을 작성하시오.