Дано множество из S точек на плоскости. Это множество не включает начала координат O(0, 0), а для каждых двух различных точек A и B из множества треугольник OAB имеет строго положительную площадь.
Рассмотрим множество пар точек (P1, P2), (P3, P4), ..., (P2k - 1, P2k). Назовем такое множество хорошим тогда и только тогда, когда:
- k ≥ 2.
- Все Pi различные и каждая точка Pi является элементом S.
- Для любых двух пар (P2i - 1, P2i) и (P2j - 1, P2j) описанные окружности треугольников OP2i - 1P2j - 1 и OP2iP2j имеют единственную общую точку, и описанные окружности треугольников OP2i - 1P2j и OP2iP2j - 1 имеют единственную общую точку.
Вычислите количество хороших множеств пар точек по модулю 1000000007 (109 + 7).
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
-46 46 0 36
0 20 -24 48
-50 50 -49 49
-20 50 8 40
-15 30 14 28
4 10 -4 5
6 15 8 10
-20 50 -3 15
4 34 -16 34
16 34 2 17
|
2
|
|
2
|
10
30 30 -26 26
0 15 -36 36
-28 28 -34 34
10 10 0 4
-8 20 40 50
9 45 12 30
6 15 7 35
36 45 -8 20
-16 34 -4 34
4 34 8 17
|
4
|
|
3
|
10
0 20 38 38
-30 30 -13 13
-11 11 16 16
30 30 0 37
6 30 -4 10
6 15 12 15
-4 5 -10 25
-16 20 4 10
8 17 -2 17
16 34 2 17
|
10
|