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

У Бесі є 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 вона намалювала рівно три нових відрізки. Порахуйте кількість перестановок, які Бесі могла обрати на першому кроці, що задовольняють цій умові, за модулем 10^9 + 7.

Вхідні дані

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

Кожен з наступних n рядків містить два цілі числа x[i] і y[i].

Вихідні дані

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

Приклад 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) у будь-якому порядку.

Приклади