众所周知，搜索引擎需要强有力的硬件支持，在进行“跳找”的开发之前，你计划先调查一下跳蚤王国的硬件技术储备。

在取得跳蚤国王的许可后，你在硬件科技中心把档案翻了个遍，偶然发现了一款非常神奇的处理器“Jumptel D233”。

这款处理器有着较低的热功比，在通常使用时，大量处理器集成在同一个主板上，且分布为 $n$ 行 $m$ 列。

若给处理器分配多线程并行计算任务，由于夸张的频率波动，各个处理器完成任务所需时间不尽相同。

具体的，对于每个处理器，其会在 $[0, 1)$ 中独立均匀随机的某个实数时刻 $p$ 完成计算。处理器之间互不影响。在完成计算之后，处理器会持续亮灯。你可以认为灯亮灭的切换不需要时间。

你经过观察发现，整行（或列）处理器的亮灭情况会对主板供电产生微妙影响。

具体地，存在 $h$ 组数对，令第 $i$ 组为 $(x_i,y_i)$；对于某种亮灭状态，若存在一个 $i$，满足恰好分别有 $x_i$ 行和 $y_i$ 列的处理器全部亮灯（可以存在其它行或列的处理器有亮灯，但不能存在另外的行或列处理器全部亮灯），则称该状态为节能态。

在节能态触发时，假如当前已经有 $k$ 个处理器亮起，那么每单位时间会节省 $F_k$ 单位电量。其中数列 $\left\{F_n\right\}_{n \ge 0}$ 被以下递推式确定：$F_0=F_1=1;\ F_n=F_{n-1}+F_{n-2}\ (n>1)$

为了评估节电效果，请你求出节省电量数的期望对 $998244353$ 取模的结果。

输入格式

第一行三个整数，分别表示 $n, m, h$，意义如题目所述。

下面 $h$ 行，第 $i$ 行为两个整数 $(x_i,y_i)$，是题中所述的与节能态相关的参数。（保证各个 $(x_i,y_i)$ 作为有序对互不相同）

输出格式

一行一个整数，表示节省电量数的期望对 $998244353$ 取模的结果。即如果答案的最简分数表示为 $\frac{x}{y}(x \geq 0, y \geq 1, \gcd(x,y) = 1)$，你需要输出满足 $ay \equiv x \pmod{998244353}$ 的那个唯一的整数 $a$ 满足 $0 \le a < 998244353$。

样例一

input

1 1 1
0 0

output

499122177

explanation

唯一的一个处理器亮灯之前为节能态。

节能态的持续时间是一在 $[0,1)$ 内均匀随机的变量，其期望为 $\frac{1}{2}=499122177\pmod{998244353}$，对节省电量数的贡献系数是 $F_0=1$。

样例二

input

2 2 1
1 1

output

798595483

explanation

$\rm O$ 表示亮灯, $-$ 表示未亮灯, 以下四种情况为节能态:

$\begin{bmatrix}\rm O&\rm O\\\rm O&-\end{bmatrix}$ $\begin{bmatrix}\rm O&-\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}-&\rm O\\\rm O&\rm O\end{bmatrix}$ $\begin{bmatrix}\rm O&\rm O\\-&\rm O\end{bmatrix}$

样例三

input

3 3 3
0 0
1 1
2 2

output

720162004

explanation

$\begin{bmatrix}\rm O&\rm O&-\\ \rm O&\rm O&\rm O\\-&\rm O&\rm O\end{bmatrix}$ 是一种满足数对 $(1,1)$ 的可能的节能态。

限制与约定

对于所有测试点，$0\leq x_i< n$，$0\leq y_i< m$，$1\leq n\times m\leq 5\times 10^5\ ,1\leq h\leq n\times m$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载