An đang chơi một trò chơi sắp xếp trên bàn cờ vuông kích thước \(N \times N\) ô. An muốn đặt \(N\) con cá lên bàn cờ sao cho mỗi hàng có đúng \(1\) con cá và mỗi cột có đúng \(1\) con cá. Hỏi có bao nhiêu cách đặt khác nhau? Hai cách đặt được coi là khác nhau khi tồn tại một hàng mà vị trí cột của con cá ở hàng đó khác nhau giữa hai cách.

Định dạng đầu vào

• Dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N \le 8\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là số cách đặt khác nhau.

Ví dụ

Input:

3

Output:

6

Giải thích: Có \(3! = 6\) cách sắp xếp \(3\) con cá vào bàn cờ \(3 \times 3\) sao cho không có hai con cá nào cùng hàng hoặc cùng cột.

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 4\).
• \(30\%\) số điểm ứng với \(N \le 6\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.