E. Раскраска
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы $$$n$$$ точек на плоскости, координаты $$$i$$$-й из них — $$$(x_i, y_i)$$$. Ни у каких двух точек не совпадают координаты.

Расстояние между точками $$$i$$$ и $$$j$$$ определено как $$$d(i,j) = |x_i - x_j| + |y_i - y_j|$$$.

Для каждой точки необходимо выбрать цвет — целое число от $$$1$$$ до $$$n$$$. Для каждой упорядоченной тройки различных точек $$$(a,b,c)$$$ должны выполняться следующие условия:

  • если $$$a$$$, $$$b$$$ и $$$c$$$ покрашены в одинаковый цвет, то $$$d(a,b) = d(a,c) = d(b,c)$$$;
  • если $$$a$$$ и $$$b$$$ покрашены в одинаковый цвет, а цвет $$$c$$$ отличен от цвета $$$a$$$, то $$$d(a,b) < d(a,c)$$$ и $$$d(a,b) < d(b,c)$$$.

Посчитайте количество различных способов выбрать цвета, чтобы удовлетворить данные условия.

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

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество точек.

Затем следуют $$$n$$$ строк. В $$$i$$$-й из них записаны два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^8$$$).

Ни у каких двух точек не совпадают координаты (т. ею если $$$i \ne j$$$, то либо $$$x_i \ne x_j$$$, либо $$$y_i \ne y_j$$$).

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

Выведите одно целое число — количество различных способов выбрать цвета точек. Так как оно может быть довольно велико, выведите его остаток от деления на $$$998244353$$$.

Примеры
Входные данные
3
1 0
3 0
2 1
Выходные данные
9
Входные данные
5
1 2
2 4
3 4
4 4
1 3
Выходные данные
240
Входные данные
4
1 0
3 0
2 1
2 0
Выходные данные
24
Примечание

В первом тесте подходят следующие способы выбрать цвета:

  • $$$[1, 1, 1]$$$;
  • $$$[2, 2, 2]$$$;
  • $$$[3, 3, 3]$$$;
  • $$$[1, 2, 3]$$$;
  • $$$[1, 3, 2]$$$;
  • $$$[2, 1, 3]$$$;
  • $$$[2, 3, 1]$$$;
  • $$$[3, 1, 2]$$$;
  • $$$[3, 2, 1]$$$.