Berland 森林是几十年前种植的,形成一个无限网格,每个单元中有一棵树。现在树木已经长大,形成了相当密集的结构。
事实上,如此密集,以至于火灾对森林构成了真正的危险。这个季节伯兰德异常炎热,一些树木着火了!
第二次起火被视为第二次$$$0$$$。每第二次火灾都会点燃所有完好无损的邻近树木以及每棵正在燃烧的树木。如果这棵树相邻或相邻的角单元相邻,则该树是相邻的。幸运的是,经过$$$t$$$秒后,Berland消防队终于到达了起火地点并立即将其全部扑灭。
现在他们想要计算火灾的破坏力。令 $$$val_{x, y}$$$ 为单元格 $$$(x, y)$$$ 中第二棵着火的树。破坏力是所有 $$$(x, y)$$$ 被烧毁树木的 $$$val_{x, y}$$$ 之和。
显然,消防部门的工作人员都是消防员,而不是程序员,因此他们要求你帮助他们计算火灾的破坏力。
结果可能相当大,因此打印它对 $$$998244353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$t$$$ ($$$1 \le n \le 50$$$, $$$0 \le t \le 10^8$$$) — 分别是最初着火的树木数量和消防部门扑灭火灾的时间。
接下来的 $$$n$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^8 \le x, y \le 10^8$$$) — 最初着火的树的位置。
显然,单元格 $$$(0, 0)$$$ 在网格上的位置和轴的方向是无关的,因为网格是无限的,答案不依赖于它们。
保证所有给定的树位置都是成对不同的。
网格是无限的,因此一旦达到 $$$-10^8$$$ 或 $$$10^8$$$,火就不会停止。它继续超出这些边界。
输出
打印一个整数 — 所有 $$$(x, y)$$$ 烧毁树木的 $$$val_{x, y}$$$ 之和以 $$$998244353$$$ 为模。
示例
输入 #1
1 2 10 11
输出 #1
40
输入 #2
4 1 2 2 1 3 0 2 2 4
输出 #2
18
输入 #3
3 0 0 0 -2 1 1 1
输出 #3
0
注意
这是前三个示例。灰色单元格的 $$$val = 0$$$,橙色单元格的 $$$val = 1$$$,红色单元格的 $$$val = 2$$$。