Каждый день Фермер Джон обходит свою ферму, чтобы проведать N (1 <= N <= 10) своих коров.
Местоположение каждой из его коров описывается точкой на координатной плоскости, а ФД начинает в точке (0,0). Чтобы сделать маршрут более интересным, ФД ходит только параллельно осям координат (на север, юг, восток и запад). Он меняет направление своего движения, только когда он добирается до одной из коров. Если пожелает, он может не менять направление своего движения, проходя через местоположение коровы. Когда ФД меняет направление движения, он может менять его на 90 или 180 градусов. ФД должен вернутся в исходную точку после посещения всех коров.
Пожалуйста, вычислите общее количество способов, которыми ФД может посетить всех своих коров, если он изменит направление своего движения ровно один раз у каждой коровы. Не изменяя направление движения, он может ходить мимо коровы произвольное количество раз. Один и тот же геометрический путь, пройденный в прямом и обратном направлениях, считается как два различных маршрута.
PROBLEM NAME: connect
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x и y координаты (разделенные пробелом) для i-ой точки(все числа в диапазоне -1000...1000).
Формат выходных данных
* Строка 1: Количество различных маршрутов ФД (может быть равным 0, если их нет)
Примечание
Всего есть два различных маршрута 1-2-4-3 или 3-4-2-1 прежде чем ФД вернется в точку (0,0).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 1
2 1
2 0
2 -5
|
2
|