分数: 600 点
问题陈述
我们有一个无限六边形网格,如下所示。

六边形单元表示为 (i,j) 有两个整数 i 和 j.
细胞 (i,j) 与以下六个单元格相邻:
- (i-1,j-1)
- (i-1,j)
- (i,j-1)
- (i,j+1)
- (i+1,j)
- (i+1,j+1)
让我们定义两个单元格之间的距离 X 和 Y 从单元格出发所需的最少移动次数 X 到单元格 Y 通过重复移动到相邻单元格。
例如,单元格之间的距离 (0,0) 和 (1,1) is 1,以及单元格之间的距离 (2,1) 和 (-1,-1) is 3.
你被给予 N 细胞 (X_1,Y_1),\ldots,(X_N,Y_N).
有多少种方式可以从这些中选择一种或多种 N 单元格,使得任意两个所选单元格之间的距离最多为 D?
求计数模数 998244353.
约束
- 1 \leq N \leq 300
- -10^9\leq X_i,Y_i \leq 10^9
- 1\leq D \leq 10^{10}
- (X_i,Y_i) 成对不同。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N D X_1 Y_1 \vdots X_N Y_N
输出
打印答案。
示例输入 1
3 1 0 0 0 1 1 0
示例输出 1
5
所选单元格有五种可能的集合: \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},和 \{(0,0),(1,0)\}.
示例输入 2
9 1 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
示例输出 2
33
示例输入 3
5 10000000000 314159265 358979323 846264338 -327950288 -419716939 937510582 -97494459 -230781640 628620899 862803482
示例输出 3
31