409803: GYM103765 H 紧急补给

谭雅·提古雷查夫少校是一位身经百战却十分遗憾的军人,她现在莱茵战线打堑壕战,但是她十分缺少补给,于是她在脑中随机选择了一个补给点( 她知道有哪几个补给,但是没记住在哪里 ),并临时查阅地图,准备前往该补给点补给(不要问我为什么不找最近一个,你要是会这个,就无敌了)。现在,少校有了一个有趣的想法,如果脑中选取补给点的概率对各个补给点而言是均匀的且其当前在地图上的位置的概率也是均匀的,那么她需要前往的补给点的距离的期望值是多少？

地图是一个边长为N的(共计(N + 1) × (N + 1)个点)的正方形,且因为莱茵战线到处都是枪林弹雨的影响,谭雅不得不通过堑壕行动,而堑壕横平竖直地连接着地图上的各个整数点,即点(x₁, y₁)到(x₂, y₂)的距离是abs({x₁ - x₂}) + abs({y₁ - y₂}),且谭雅的当前位置和补给点的坐标也全都是整数.

一行给出一个正整数N和一个正整数M分别表示地图的尺寸和补给点的数量.

接下来的M行依次给出x_i,y_i,即第i个补给点的坐标.

数据范围:1 ≤ N ≤ 2·10⁶ 1 ≤ M ≤ 2·10⁶ 0 ≤ x_i, y_i ≤ N

输入保证每一个补给点的坐标都是独一无二的,即同一个点不会同时存在两个补给点

对于每一个答案 x / y ,请输出最小的一个正整数 k 使得 y·k ≡ x(mod 998244353)

2 1
0 0

2

6 3
0 0
5 3
0 3

760567131

第一个样例中距离补给点(0, 0)为0的点有(0, 0)；

距离为1的点有(0, 1), (1, 0)；

距离为2的点有(0, 2), (1, 1), (2, 0)；

距离为3的点有(1, 2), (2, 1)；

距离为4的点为(2, 2)。

所以距离的期望为