У Бесі є \(N\) (\(3\le N\le 40\))улюблених точок на 2D-гратці, ніякі три з яких не колінеарні. Для кожного \(1\le i\le N\), \(i\)-а точка задається двома цілими координатами \(x_i\) і \(y_i\) (\(0\le x_i,y_i\le 10^4\)).

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

1. Вона вибирає деяку перестановку \(p_1,p_2,\ldots,p_N\) з \(N\) точок
2. Вона будує відрізки між \(p_1\) і \(p_2\), \(p_2\) і \(p_3\), \(p_3\) і \(p_1\).
3. Потім для кожного цілого \(i\) від \(4\) до \(N\) по порядку, вона будує відрізки прямих від \(p_i\) до \(p_j\) lzk всіх \(j<i\) так, цей відрізок не перетинає жодної з раніше побудованих відрізків (поза кінцевими точками)

Бесі помітила, що для кожного \(i\) вона побудувала рівно три нові відрізки. Обчисліть кількість перестановок, які Бесі могла вибрати на кроці 1, які задовольняють цій властивості за модулем \(10^9+7\).

Формат вхідних даних

Перший рядок містить \(N\).

Кожен з наступних \(N\) рядків містить два розділені пробілом цілих числа \(x_i\) і \(y_i\).

Формат вихідних даних

Кількість перестановок за модулем \(10^9+7\).

Приклад вхідних даних

4
0 0
0 4
1 1
1 2

Приклад вихідних даних

0

Приклад вхідних даних

4
0 0
0 4
4 0
1 1

Приклад вихідних даних

24

Все перестановки працюють.

Приклад вхідних даних

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)\), \((1,1)\), \((1,2)\), та \((0,4)\) у деякому порядку.

ОЦІНЮВАННЯ:

• У тестах 1-6 \(N\le 8\).
• У тестах 7-20 немає додаткових обмежень.