← 返回题目列表

Codeforces · 1290/F

F. 制作形状

中文机器翻译题面 查看原题

给你 $$$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

注意

第一个样本的形状为:

第二个样本的唯一形状是:

第四个样本的唯一形状是: