Hoán Vị Tam Giác

Cho $N$ điểm phân biệt trên mặt phẳng tọa độ, không có ba điểm nào thẳng hàng. Bessie vẽ các đoạn thẳng theo quy trình sau:

1. Chọn một hoán vị $p_1,p_2,\dots ,p_N$ của $N$ điểm
2. Vẽ tam giác $p_1{p}_2{p}_3$ (3 đoạn thẳng)
3. Với mỗi $i$ từ 4 đến $N$: vẽ các đoạn thẳng từ $p_i$ đến các điểm $p_j$ ($j<i$) sao cho đoạn mới không cắt bất kỳ đoạn nào đã vẽ (trừ tại đầu mút)

Điều kiện: Ở mỗi bước $i\ge 4$, phải vẽ được đúng 3 đoạn thẳng mới.

Hãy đếm số hoán vị hợp lệ, modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Hai số nguyên $x_i,y_i$ — tọa độ điểm thứ $i$

Dữ liệu ra

Một số nguyên: số hoán vị hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $3\le N\le 40$
• $0\le x_i,y_i\le {10}^4$
• Không có ba điểm nào thẳng hàng

Ví dụ