#P17793. Making Shapes

Making Shapes

题目描述

给定 nn 个两两不共线的二维向量。你可以用以下方式在二维平面上用这些向量构造图形:

  1. 从原点 (0,0)(0, 0) 开始。
  2. 选择一个向量,将该向量的线段加到当前点。例如,如果当前点在 (x,y)(x, y),你选择向量 (u,v)(u, v),则从当前点画一条线段到 (x+u,y+v)(x + u, y + v),并将当前点更新为 (x+u,y+v)(x + u, y + v)。
  3. 重复第 2 步,直到你再次回到原点。

每个向量可以重复使用任意多次。

请计算可以用上述步骤构造出的不同的、非退化(面积大于 00)且凸的图形的数量,要求这些图形的构成向量按逆时针顺序排列,并且该图形可以通过平移被包含在一个 m×mm \times m 的正方形内。由于答案可能很大,请对 998244353998244353 取模。

如果存在某种平行移动能使第一个图形与第二个图形重合,则认为这两个图形是相同的。

如果存在某种平行移动,使得图形内或边界上的每个点 (u,v)(u, v) 都满足 0≤u,v≤m0 \leq u, v \leq m,则认为该图形可以被包含在 m×mm \times m 的正方形内。

输入格式

第一行包含两个整数 nn 和 mm,分别表示向量的数量和正方形的边长(1≤n≤51 \leq n \leq 5,1≤m≤1091 \leq m \leq 10^9)。

接下来的 nn 行,每行包含两个整数 xix_i 和 yiy_i,表示第 ii 个向量的 xx 坐标和 yy 坐标(∣xi∣,∣yi∣≤4|x_i|, |y_i| \leq 4,(xi,yi)≠(0,0)(x_i, y_i) \neq (0, 0))。

保证任意两个向量都不平行,即对于任意 1≤i<j≤n1 \leq i < j \leq n,不存在实数 kk 使得 xi⋅k=xjx_i \cdot k = x_j 且 yi⋅k=yjy_i \cdot k = y_j。

输出格式

输出一个整数,表示满足条件的图形数量,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

3 3
-1 0
1 1
0 -1

输出 #1

3

输入输出样例 #2

输入 #2

3 3
-1 0
2 2
0 -1

输出 #2

1

输入输出样例 #3

输入 #3

3 1776966
-1 0
3 3
0 -2

输出 #3

296161

输入输出样例 #4

输入 #4

4 15
-4 -4
-1 1
-1 -4
4 3

输出 #4

1

输入输出样例 #5

输入 #5

5 10
3 -4
4 -3
1 -3
2 -3
-3 -4

输出 #5

0

输入输出样例 #6

输入 #6

5 1000000000
-2 4
2 -3
0 -4
2 4
-1 -3

输出 #6

9248783

说明/提示

第一个样例的所有图形如下:

第二个样例的唯一图形如下:

第四个样例的唯一图形如下: