配点 : 500 点
問題文
整数 K 和 按字典顺序比较 3 在维度为 N 点 (x_1,y_1,z_1), \dots, (x_N,y_N,z_N) 。 对于
N 点 (K x_1,K y_1,K z_1), \dots, (K x_N,K y_N,K z_N) 的凸包内部或边界内,且坐标均为整数的点的数量为 998244353 后求余数。
制約
- 所有输入均为整数
- 4 \leq N \leq 100
- 1 \leq K \leq 10^{15}
- \sout{-2 \times 10^3 \leq x_i,y_i,z_i \leq 2 \times 10^3} (1 ≤ i ≤ N)
- \color{red}-2 \times 10^2 \leq x_i,y_i,z_i \leq 2 \times 10^2 (1 ≤ i ≤ N)
- (x_i,y_i,z_i) \neq (x_j,y_j,z_j) (1 ≤ i < j ≤ N)
- N 没有平面可以经过所有
入力
输入是按以下格式从标准输入给出的。
N K x_1 y_1 z_1 \vdots x_N y_N z_N
出力
打印答案。 来自
入力例 1
4 2 0 0 0 1 0 0 0 1 0 0 0 1
出力例 1
10
4 点 (0,0,0),(2,0,0),(0,2,0),(0,0,2) 凸包内部和边界上坐标为整数的点。 (0,0,0),(1,0,0),(2,0,0),(0,1,0),(1,1,0),(0,2,0),(0,0,1),(1,0,1),(0,1,1),(0,0,2) 可以得到第 10 件。
入力例 2
4 10000 0 0 0 1 0 0 0 1 0 0 0 1
出力例 2
59878050
4 点 (0,0,0),(10000,0,0),(0,10000,0),(0,0,10000) 凸包内包含坐标为整数的点为 166\,766\,685\,001 个,因此得到 998244353 余数除以 59878050 。
入力例 3
8 314159265358979 5 -3 -3 -5 -3 -3 0 5 -3 0 0 10 4 2 6 -4 2 6 0 -5 6 0 0 -5
出力例 3
152811018