У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 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.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x
i и y
i.
Выходные данные:
Количество перестановок по модулю 10
9+7.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4
0 0
0 4
1 1
1 2 |
0 |
Никакая перестановка не сработает. |
| 2 |
4
0 0
0 4
4 0
1 1 |
24 |
Все перестановки работают. |
| 3 |
5
0 0
0 4
4 0
1 1
1 2 |
96 |
Одна из перестановок, удовлетворяющих свойству - (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)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке. |