给你 $$$n$$$ 成对的非共线二维向量。您可以通过以下方式使用这些向量在二维平面中制作形状:
1. 从原点 $$$(0, 0)$$$ 开始。
2. 选择一个向量并将该向量的片段添加到当前点。例如,如果当前点位于 $$$(x, y)$$$,并且选择向量 $$$(u, v)$$$,则从当前点到 $$$(x + u, y + v)$$$ 处的点绘制一条线段,并将当前点设置为 $$$(x + u, y + v)$$$。
3. 重复步骤 2,直到再次到达原点。
您可以根据需要多次重复使用矢量。
计算通过应用这些步骤而形成的不同的、非退化的(面积大于 $$$0$$$)和凸形状的数量,使得该形状可以包含在 $$$m \times m$$$ 正方形内,并且构建该形状的向量是逆时针方向的。由于这个数字可能太大,您应该通过模 $$$998244353$$$ 来计算它。
如果第一个形状到另一个形状存在某种平行平移,则两个形状被认为是相同的。
如果形状存在某种平行平移,则形状可以包含在 $$$m \times m$$$ 正方形内,使得形状内部或边界上的每个点 $$$(u, v)$$$ 满足 $$$0 \leq u, v \leq m$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ — 向量的数量和正方形的大小($$$1 \leq n \leq 5$$$, $$$1 \leq m \leq 10^9$$$)。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 向量的 $$$x$$$ 坐标和 $$$y$$$ 坐标 ($$$|x_i|, |y_i| \leq 4$$$, $$$(x_i, y_i) \neq (0, 0)$$$)。
保证没有两个向量是平行的,因此对于任何两个索引 $$$i$$$ 和 $$$j$$$ 使得 $$$1 \leq i < j \leq n$$$,不存在实数值 $$$k$$$ 使得 $$$x_i \cdot k = x_j$$$ 和 $$$y_i \cdot k = y_j$$$。
输出
输出一个整数——可满足形状的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
3 3 -1 0 1 1 0 -1
输出 #1
3
输入 #2
3 3 -1 0 2 2 0 -1
输出 #2
1
输入 #3
3 1776966 -1 0 3 3 0 -2
输出 #3
296161
输入#4
4 15 -4 -4 -1 1 -1 -4 4 3
输出#4
1
输入 #5
5 10 3 -4 4 -3 1 -3 2 -3 -3 -4
输出 #5
0
输入 #6
5 1000000000 -2 4 2 -3 0 -4 2 4 -1 -3
输出 #6
9248783
注意
第一个样本的形状为:
第二个样本的唯一形状是:
第四个样本的唯一形状是: