题目描述
有一片 $R\times C$ 的空地,即左下角 $(0,0)$,右上角 $(R,C)$ 的矩形地块,要在这里修建两个祭坛。
祭坛可以描述为一个矩形,其四边平行于坐标轴,且顶点均为整点。一个祭坛的入口在某一侧边上正中间的位置,两个祭坛的入口必须相反,即一个在西侧,另一个就在东侧,或者一个在北侧,则另一个必须在南侧。
修建的两个祭坛的边界与内部都是不能相交的,经探测,有 $N$ 个位置的右上角为 $(x,y)$ 的 $1\times 1$ 的土地是不适合修建祭坛的,祭坛不能包含这些位置(但边可以重合)。
祭坛修建之后,还要在两个入口的连线修建一条道路,道路也不可以与祭坛内部或边界相交。
满足上述条件的祭坛及道路修建方案即为合法的。请求出不同合法方案的个数模 $998244353$。方案不同当且仅当一种方案中一个格子被包含在祭坛内,而另一种方案未被包含,或者道路的两端点位置不同。
输入格式
第一行三个整数 $R,C,N$ 表示空地的大小及不可修建祭坛的格子数。
接下来 $N$ 行每行两个整数 $(x,y)$ 表示一个不适合修建祭坛的格子的右上角坐标。
输出格式
一个整数,表示道路的合法方案数模 $998244353$。
数据范围
Subtask1(1%) $R,C\leq 10$
Subtask2(7%) $R,C\leq 5000$
Subtask3(21%) 保证数据随机
Subtask4(31%) $R,C,N\le 50000$
Subtask5(40%) $R,C\le 300000,N\le 100000$
对于所有数据,满足 $R,C\le 300000,N\le 100000$,$1\le x \le R,1\le y \le C$,且$(x,y)$两两不同。