Bessie có \(N\) điểm phân biệt yêu thích trên lưới hai chiều (\(3\le N\le40\)), trong đó không có ba điểm nào thẳng hàng. Với mỗi \(1\le i\le N\), điểm thứ \(i\) được biểu diễn bằng hai số nguyên \(x_i\) và \(y_i\) (\(0\le x_i,y_i\le10^4\)).

Bessie vẽ một số đoạn thẳng giữa các điểm như sau:

1. Cô chọn một hoán vị \(p_1,p_2,\ldots,p_N\) của \(N\) điểm.
2. Cô vẽ các đoạn thẳng nối \(p_1\) với \(p_2\), \(p_2\) với \(p_3\), và \(p_3\) với \(p_1\).
3. Sau đó, lần lượt với mỗi số nguyên \(i\) từ \(4\) đến \(N\), cô vẽ đoạn thẳng từ \(p_i\) đến \(p_j\) với mọi \(j<i\) sao cho đoạn thẳng đó không giao với bất kỳ đoạn thẳng nào đã vẽ trước đó, ngoại trừ tại các đầu mút.

Bessie nhận thấy với mỗi \(i\), cô đã vẽ đúng ba đoạn thẳng mới. Hãy tính số hoán vị mà Bessie có thể đã chọn ở bước 1 và thỏa mãn tính chất này, lấy phần dư theo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\) cách nhau bởi dấu cách.

Dữ liệu ra

In số hoán vị lấy phần dư theo \(10^9+7\).

Phân nhóm

• Các test 1-6 thỏa mãn \(N\le8\).
• Các test 7-20 không có ràng buộc bổ sung.

Ví dụ

4
0 0
0 4
1 1
1 2

0

4
0 0
0 4
4 0
1 1

24

5
0 0
0 4
4 0
1 1
1 2

96

Giải thích ví dụ 1. Không có hoán vị nào thỏa mãn.

Giải thích ví dụ 2. Mọi hoán vị đều thỏa mãn.

Giải thích ví dụ 3. Một hoán vị thỏa mãn tính chất là \((0,0),(0,4),(4,0),(1,2),(1,1)\). Với hoán vị này:

1. Đầu tiên, Bessie vẽ các đoạn thẳng giữa mọi cặp điểm trong \((0,0),(0,4)\) và \((4,0)\).
2. Sau đó, cô vẽ các đoạn thẳng từ \((0,0)\), \((0,4)\) và \((4,0)\) đến \((1,2)\).
3. Cuối cùng, cô vẽ các đoạn thẳng từ \((1,2)\), \((4,0)\) và \((0,0)\) đến \((1,1)\).

Hình minh họa:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_5fb5745a.png

Hoán vị không thỏa mãn tính chất nếu bốn điểm đầu tiên là \((0,0)\), \((1,1)\), \((1,2)\) và \((0,4)\) theo một thứ tự bất kỳ.

Nguồn

USACO 2021 US Open, Gold - Permutation: https://usaco.org/index.php?page=viewproblem2&cpid=1139

Tác giả: Benjamin Qi.