Permutation
Permutation
Bessie has n favorite distinct points on a 2D grid, no three of which are collinear. For each i (1 ≤ i ≤ n), the i-th point is denoted by two integers xi
and yi
(0 ≤ xi
, yi
≤ 104
).
Bessie draws some segments between the points as follows.
- She chooses some permutation
p1
,p2
, ..,pn
of the n points. - She draws segments between
p1
andp2
,p2
andp3
,p3
andp1
. - Then for each integer i from 4 to n in order, she draws a line segment from
pi
topj
for all j < i such that the segment does not intersect any previously drawn segments (aside from at endpoints).
Bessie notices that for each i, she drew exactly three new segments. Compute the number of permutations Bessie could have chosen on step 1 that would satisfy this property, modulo 109
+ 7.
Input
The first line contains n (3 ≤ n ≤ 40).
Followed by n lines, each containing two integers xi
and yi
.
Output
The number of permutations modulo 109
+ 7.
Example 1
No permutations work.
Example 2
All permutations work.
Example 3
One permutation that satisfies the property is (0, 0), (0, 4), (4, 0), (1, 2), (1, 1). For this permutation,
First, she draws segments between every pair of (0, 0), (0, 4) and (4, 0).
Then she draws segments from (0, 0), (0, 4), and (4, 0) to (1, 2).
Finally, she draws segments from (1, 2), (4, 0), and (0, 0) to (1, 1).
The permutation does not satisfy the property if its first four points are (0, 0), (1, 1), (1, 2) and (0, 4) in some order.
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