JOI rất thích quan sát bầu trời đêm. Gần như mỗi tối, cậu đều ngắm sao và tìm hiểu mỗi ngôi sao thuộc chòm sao nào.

Một tối nọ, JOI phát hiện \(N\) ngôi sao mà cậu chưa từng thấy. Cậu chụp ảnh bầu trời rồi đến thư viện tìm hiểu vào ngày hôm sau. JOI biết rằng tất cả các ngôi sao này đều thuộc một trong hai chòm sao \(A\) và \(B\), đồng thời xác định được chòm sao của một số ngôi sao. Với những ngôi sao còn lại, cậu chưa biết chúng thuộc chòm sao nào.

Có thể coi mỗi ngôi sao là một điểm trên ảnh. Một chòm sao gồm ít nhất một ngôi sao cùng một số đoạn thẳng nối các cặp sao của chòm sao đó, sao cho:

• Từ bất kỳ ngôi sao nào của một chòm sao, có thể đi đến bất kỳ ngôi sao nào khác của cùng chòm sao bằng cách đi theo các đoạn thẳng của chòm sao đó.
• Một đoạn thẳng của chòm sao này không được giao với một đoạn thẳng của chòm sao kia.

Một ngôi sao đứng riêng cũng được coi là một chòm sao. Không có ba ngôi sao nào thẳng hàng trên ảnh. Mỗi ngôi sao trong \(N\) ngôi sao thuộc đúng một trong hai chòm sao \(A\) và \(B\), và hai chòm sao này không chứa ngôi sao nào khác ngoài \(N\) ngôi sao đã cho.

Yêu cầu

Hãy tính số cách chọn hai tập hợp sao tạo thành chòm sao \(A\) và chòm sao \(B\), phù hợp với những thông tin đã biết và có thể nối các sao để thỏa mãn các điều kiện trên. Cả hai chòm sao đều phải không rỗng. Chỉ phân biệt các cách theo tập hợp sao của mỗi chòm sao; các cách vẽ đoạn thẳng khác nhau trên cùng hai tập hợp chỉ được tính một lần. In ra phần dư của số cách khi chia cho \(1\,000\,000\,007=10^9+7\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số ngôi sao JOI phát hiện.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa ba số nguyên \(X_i,Y_i,C_i\) cách nhau bởi dấu cách. \((X_i,Y_i)\) là tọa độ ngôi sao thứ \(i\) trên ảnh.

Giá trị \(C_i\) có ý nghĩa như sau:

• \(C_i=0\): chưa biết ngôi sao thứ \(i\) thuộc chòm sao nào.
• \(C_i=1\): ngôi sao thứ \(i\) thuộc chòm sao \(A\).
• \(C_i=2\): ngôi sao thứ \(i\) thuộc chòm sao \(B\).

Dữ liệu ra

In ra trên một dòng phần dư của số cách chọn hai tập hợp sao khi chia cho \(1\,000\,000\,007\). Nếu không có cách nào thỏa mãn, in ra 0.

Ràng buộc

• \(2\le N\le100\,000\).
• \(0\le X_i\le10^9\) và \(0\le Y_i\le10^9\) với \(1\le i\le N\).
• \(C_i\in\{0,1,2\}\) với \(1\le i\le N\).
• Không có ba ngôi sao nào nằm trên cùng một đường thẳng.
• Mọi giá trị trong đầu vào đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le10\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn \(N\le300\).

Ví dụ

4
1 1 1
2 1 1
1 2 0
2 2 2

2