問題文

整数 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 個の点すべてを通る平面は存在しない

入力例 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