Заданы \(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)\).
Посчитайте количество различных способов выбрать цвета, чтобы удовлетворить данные условия.
Выходные данные
Выведите одно целое число — количество различных способов выбрать цвета точек. Так как оно может быть довольно велико, выведите его остаток от деления на \(998244353\).
Примечание
В первом тесте подходят следующие способы выбрать цвета:
- \([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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 0
3 0
2 1
|
9
|
|
2
|
5
1 2
2 4
3 4
4 4
1 3
|
240
|
|
3
|
4
1 0
3 0
2 1
2 0
|
24
|