使用六边形网格 2

题目描述

有一个如下所示的无限六边形网格。

六边形格子用两个整数 $(i,j)$ 表示。

格子 $(i,j)$ 与以下 6 个格子相邻:

$(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)$ 之间的距离为 $1$,格子 $(2,1)$ 与 $(-1,-1)$ 之间的距离为 $3$。

给定 $N$ 个格子 $(X_1,Y_1),\ldots,(X_N,Y_N)$。

从这 $N$ 个格子中选取一个或多个格子,使得所选格子中任意两个格子之间的距离至多为 $D$,共有多少种选法?

请输出答案对 $998244353$ 取模的值。

输入格式

输入按以下格式从标准输入给出:

$N$ $D$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

输出格式

输出答案。

样例

3 1
0 0
0 1
1 0

5

所选格子的集合共有五种可能:$\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}$,以及 $\{(0,0),(1,0)\}$。

9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

33

5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482

31

数据范围

• $1 \le N \le 300$
• $-10^9 \le X_i, Y_i \le 10^9$
• $1 \le D \le 10^{10}$
• $(X_i,Y_i)$ 两两不同。
• 输入中的所有值均为整数。