Kućice

Όλοι γνωρίζουν ότι κάθε άλλο περίπτερο στη χριστουγεννιάτικη αγορά του Ζάγκρεμπ στην πραγματικότητα στήθηκε απλά τραβώντας τα σωστά σχοινιά. Φέτος οι αρχές αποφάσισαν να στείλουν επιθεώρηση για να τιμωρήσουν τα περίπτερα που είχαν στηθεί παράνομα.

Υπάρχουν ~n~ περίπτερα, τα οποία μπορούν να αναπαρασταθούν με σημεία στο επίπεδο, όπου κανένα από αυτά δεν βρίσκεται στην ίδια ευθεία. Οι αρχές θα αναγνωρίσουν τα περίπτερα που διέπονται από διαφθορά και θα τα αποκόψουν από την υπόλοιπη πόλη με φράκτη. Ο φράκτης θα περιβάλλει τους αναφερόμενους θαλάμους και θα έχει το σχήμα του μικρότερου κυρτού πολυγώνου που θα τα περιέχει όλα. Με άλλα λόγια, ο φράκτης μπορεί να θεωρηθεί ως το όριο της κυρτής περίφραξης του επιλεγμένου συνόλου σημείων. Δυστυχώς, είναι πιθανό μερικά από τα μη παράνομα περίπτερα να περιφραχθούν επίσης.

Πριν από τον έλεγχο της περιοχής, οι αρχές εκτιμούν ότι η πιθανότητα διαφθοράς οποιουδήποτε περιπτέρου είναι ~50~%. Έχοντας αυτό υπόψη, αναρωτιούνται ποιος είναι ο αναμενόμενος αριθμός περιπτέρων που θα καταλήξουν να περιφραχτούν. Η αναμενόμενη τιμή ορίζεται πολλαπλασιάζοντας την πιθανότητα ενός συγκεκριμένου υποσυνόλου των περιπτέρων να επιλεχτεί, με τον αριθμό των περιπτέρων που είναι περιφραγμένα σε αυτή την περίπτωση, και αθροίζοντας τα γινόμενα για όλες τις πιθανές επιλογές του υποσυνόλου. Φυσικά, εάν το επιλεγμένο υποσύνολο αποτελείται από λιγότερα από τρία σημεία, η κυρτή περίφραξη είναι εκφυλισμένη, δηλαδή είναι ένα τμήμα, σημείο ή το κενό σύνολο.

Μπορεί να αποδειχθεί ότι η επιθυμητή αναμενόμενη τιμή μπορεί να γραφτεί με τη μορφή ~\frac{m}{2^n}~, για κάποιο θετικό ακέραιο ~2m~. Οι αρχές θα ήθελαν να μάθουν την αναμενόμενη τιμή, γι' αυτό σας ζητούν να υπολογίσετε την τιμή του ~m~. Επειδή η απάντηση μπορεί να είναι πολύ μεγάλη, θα πρέπει να εκτυπώσετε το υπόλοιπο της ακέραιας διαίρεσης του ~m~ με το ~10^9 + 7~.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n\;(1 \le n \le 1000)~, τον αριθμό των περιπτέρων.

Η ~i~-οστή των επόμενων ~n~ γραμμών περιέχει ένα ζεύγος θετικών ακεραίων ~x_i,\;y_i\;(|x_i|, |y_i| \le 10^6)~, οι οποίοι αντιπροσωπεύουν τις συντεταγμένες ~x~ και ~y~ του ~i~-οστού περιπτέρου, αντίστοιχα. Δεν υπάρχουν δύο περίπτερα που να έχουν την ίδια τοποθεσία.

Δεν υπάρχουν τρία περίπτερα στην ίδια γραμμή.

Έξοδος

Στην ίδα γραμμή τυπώστε το ~m~, που περιγράφεται πιο πάνω (modulo ~10^9 + 7~).

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	Όλα τα σημεία βρίσκονται στο όριο της κυρτής περίφραξης όλων των σημείων και ~n \ge 3~.
2	30	Όλα τα σημεία εκτός από το πρώτο βρίσκονται στο όριο της κυρτής περίφραξης όλων των σημείων, που είναι το εσωτερικό, και ~n \ge 4,\;x_1\;=\;y_1\;=\;0~.
3	10	~1 \le n \le 15~
4	30	~1 \le n \le 100~
5	30	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

1
5 5

output

1

Εξήγηση του 1ου παραδείγματος:

Υπάρχει πιθανότητα ~50~% το πρώτο και μοναδικό περίπτερο να περιφραχτεί, οπότε η αναμενόμενη τιμή είναι ~\frac{1}{2}~.

input

3
-1 -1
1 -1
0 1

output

12

Εξήγηση του 2ου παραδείγματος:

Υπάρχουν οκτώ πιθανές επιλογές για ένα υποσύνολο και ο αριθμός των περιφραγμένων περιπτέρων για αυτές τις επιλογές είναι ~0,\;1,\;1,\;1,\;2,\;2,\;2,\;3~. Επομένως, η αναμενόμενη τιμή είναι ~\frac{1}{8}(0 + 1 + 1 + 1 + 2 + 2 + 2 + 3) = \frac{12}{8}~.

input

5
0 0
-1 0
2 -1
3 2
0 3

output

83