У Беси есть n любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого i (1 ≤ i ≤ n), i-ая точка задаётся двумя целочисленными координатами xi и yi (0 ≤ xi, yi ≤ 104).

Беси рисует некоторые отрезки между точками следующим образом:

• Она выбирает некоторую перестановку p1, p2, .., pn из n точек;
• Она рисует отрезки между p1 и p2, p2 и p3, p3 и p1;
• Затем для каждого целого i от 4 до n по порядку, она рисует отрезки прямых от pi до pj для всех j < i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)

Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 109 + 7.

Входные данные

Первая строка содержит n (3 ≤ n ≤ 40).

Каждая из последующих n строк содержит два целых числа xi и yi.

Выходные данные

Количество перестановок по модулю 109 + 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) в некотором порядке.