Permutation#11239
Bessie has favorite distinct points on a 2D grid, no three of which are collinear. For each (1 \le i \le n), the -th point is denoted by two integers x_i and y_i (0 \le x_i, y_i \le 10^4).
Bessie draws some segments between the points as follows.
- She chooses some permutation p_1, p_2, .., p_n of the points. - She draws segments between p_1 and p_2, p_2 and p_3, p_3 and p_1. - Then for each integer from to in order, she draws a line segment from p_i to p_j for all j < i such that the segment does not intersect any previously drawn segments (aside from at endpoints).
Bessie notices that for each , she drew exactly three new segments. Compute the number of permutations Bessie could have chosen on step that would satisfy this property, modulo 10^9 + 7.
The first line contains (3 \le n \le 40).
Followed by lines, each containing two integers x_i and y_i.
The number of permutations modulo 10^9 + 7.
Esempio 1
Esempio 2
Esempio 3
**Example 1:** No permutations work.
**Example 2:** All permutations work.
**Example 3:** One permutation that satisfies the property is , , , , . For this permutation,
First, she draws segments between every pair of , and .
Then she draws segments from , , and to .
Finally, she draws segments from , , and to .
The permutation does not satisfy the property if its first four points are , , and in some order.