Перестановка#11239

Перестановка

1 секунда

128 мегабайтів

Дуже складна

У Бесі є $n$ улюблених точок на двовимірній решітці, жодні три з яких не лежать на одній прямій. Кожна $i$ -та точка задається двома цілими координатами $x_{i}$ x_i і $y_{i}$ y_i ( $0 \leq x_{i}, y_{i} \leq 1 0^{4}$ 0 \leq x_i, y_i \leq 10^4).

Бесі малює відрізки між точками за таким алгоритмом:

Вона обирає певну перестановку $p_{1}$ p_1, $p_{2}$ p_2, ..., $p_{n}$ p_n з $n$ точок.
Вона малює відрізки між $p_{1}$ p_1 і $p_{2}$ p_2, $p_{2}$ p_2 і $p_{3}$ p_3, а також $p_{3}$ p_3 і $p_{1}$ p_1.
Потім для кожного цілого $i$ від $4$ до $n$ , вона малює відрізки від $p_{i}$ p_i до $p_{j}$ p_j для всіх $j < i$ j < i, так щоб жоден з цих відрізків не перетинав жоден з раніше намальованих відрізків (крім кінцевих точок).

Бесі зауважила, що для кожного $i$ вона намалювала рівно три нових відрізки. Порахуйте кількість перестановок, які Бесі могла обрати на першому кроці, що задовольняють цій умові, за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить $n$ ( $3 \leq n \leq 40$ 3 \leq n \leq 40).

Кожен з наступних $n$ рядків містить два цілі числа $x_{i}$ x_i і $y_{i}$ y_i.

Вихідні дані

Виведіть кількість перестановок за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Приклад 1

Жодна перестановка не підходить.

Приклад 2

Усі перестановки підходять.

Приклад 3

Одна з перестановок, що задовольняє умови, - $(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)$ у будь-якому порядку.