Convex Hull bản 1

Cho ~n~ điểm trên mặt phảng ~O_{x,y}~ và không có ba điểm nào thẳng hàng.

Với tập con ~S~ của tập ~n~ điểm ~p_i, p_2, \ldots, p_n~ trên, ta định nghĩa bao lồi của ~S~ như sau: Bao lồi là đa giác lồi có diện tích nhỏ nhất sao cho mọi điểm của ~S~ đều nằm trong hoặc trên chu vi của đa giác đó.

Hãy lập trình đếm xem có bao nhiêu tập con ~S~ sao cho diện tích bao lồi của nó là một số nguyên.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~3 \le n \le 80~.

~n~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ là tọa độ của các điểm thỏa ~0 \le |x_i|, |y_i| \le 10^4~.

Output

In ra kết quả cần đếm, do số lớn nên modulo ~10^9+7~.

Samples

4
0 0
1 2
0 1
1 0

2

Note

Có ~2~ cấu hình phù hợp là ~\{p_1, p_2, p_4\}~ và ~\{p_2, p_3, p_4\}~.

Ref Atcoder