Заданы \(n\) точек на плоскости, координаты \(i\)-й из них — \((x_i, y_i)\). Ни у каких двух точек не совпадают координаты.
Расстояние между точками \(i\) и \(j\) определено как \(d(i,j) = |x_i - x_j| + |y_i - y_j|\).
Для каждой точки необходимо выбрать цвет — целое число от \(1\) до \(n\). Для каждой упорядоченной тройки различных точек \((a,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
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач