配点 : $600$ 点

問題文

以下のような、無限に広い六角形のグリッドがあります。

六角形のマスは $2$ つの整数 $i,j$ を用いて $(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)$

$2$ つのマス $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$ マスの中から $1$ つ以上のマスを選ぶ方法のうち、選んだマスのうちどの $2$ マスの距離も $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$

出力

答えを出力せよ。

3 1
0 0
0 1
1 0

5

選ぶマスの集合として考えられるのは $\{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},\{(0,0),(1,0)\}$ の $5$ 通りです。

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