Đếm số lượng cách đặt \(n\) quân hậu trên bàn cờ kích cỡ \(n \times n\) sao cho không có \(2\) quân hậu nào tấn công được nhau.

Ví dụ một cách đặt \(5\) quân hậu:

• X....
• ...X.
• .X...
• ....X
• ..X..

Input

• Một số nguyên \(n\).

Output

• Một số nguyên duy nhất là số lượng cách đặt \(n\) quân hậu.

Điều kiện

• \(1 \le n \le 10\)

Sample Input 1

5

Sample Output 1

10