Logo Universal Online Judge

UOJ

时间限制:6 s 空间限制:512 MB
Statistics

题目描述

有一片 $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)$两两不同。

大样例