给定平面上 $$$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$$$ 取模。
示例
输入 #1
3 1 0 3 0 2 1
输出 #1
9
输入 #2
5 1 2 2 4 3 4 4 4 1 3
输出 #2
240
输入 #3
4 1 0 3 0 2 1 2 0
输出 #3
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]$$$.