У Беси есть n любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого i (1 ≤ i ≤ n), i-ая точка задаётся двумя целочисленными координатами x[i]
и y[i]
(0 ≤ x[i]
, y[i]
≤ 10^4
).
Беси рисует некоторые отрезки между точками следующим образом:
Она выбирает некоторую перестановку p[1]
, p[2]
, .., p[n]
из n точек;
Она рисует отрезки между p[1]
и p[2]
, p[2]
и p[3]
, p[3]
и p[1]
;
Затем для каждого целого i от 4 до n по порядку, она рисует отрезки прямых от p[i]
до p[j]
для всех j < i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10^9
+ 7.
Первая строка содержит n (3 ≤ n ≤ 40).
Каждая из последующих n строк содержит два целых числа x[i]
и y[i]
.
Количество перестановок по модулю 10^9
+ 7.
Никакая перестановка не сработает.
Все перестановки работают.
Одна из перестановок, удовлетворяющих свойству - (0, 0), (0, 4), (4, 0), (1, 2), (1, 1). Для этой перстановки
Сначала она рисует отрезки между каждой парой (0, 0), (0, 4) и (4, 0).
Затем она рисует отрезки от (0, 0), (0, 4) и (4, 0) до (1, 2).
Наконец, она рисует отрезки от (1, 2), (4, 0) и (0, 0) до (1, 1).
Перестановка не удовлетворяет свойству, если её первые четыре точки (0, 0), (1, 1), (1, 2) и (0, 4) в некотором порядке.