#P18053. ICPC

ICPC

ICPC

一张纸对应平面上的矩形 [0,n]×[0,m][0,n]\times[0,m],按整数坐标划分为单位方格。纸上有 kk 块墨迹,第 ii 块占据矩形 [ai,ci]×[bi,di][a_i,c_i]\times[b_i,d_i]。

从 (0,0)(0,0) 到 (n,m)(n,m) 的每条单调格点路径由向右一步 (1,0)(1,0) 和向上一步 (0,1)(0,1) 组成。在所有这样的路径中等概率选择一条,沿它把纸分开。

求所有墨迹都完整保留在同一侧纸上的概率。路径可以沿墨迹矩形的边界行走,但不能穿过墨迹内部,也不能把不同的墨迹分在两侧。沿纸张外边界、使其中一侧为空的路径也参与随机选择。墨迹矩形可以重叠。

答案对 M=998244353M=998244353 取模:若真实概率为既约分数 p/qp/q,输出 p⋅q−1 mod Mp\cdot q^{-1}\bmod M。本题保证分母模 MM 非零。

输入格式

每个文件只有一个用例。第一行三个整数 n,m,kn,m,k,均满足 1≤n,m,k≤2×1051\le n,m,k\le2\times10^5。

接下来 kk 行,每行四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i,满足

0≤ai<ci≤n,0≤bi<di≤m.0\le a_i<c_i\le n,\qquad 0\le b_i<d_i\le m.

输出格式

输出一个整数,表示所求概率模 998244353998244353 的值。

样例

输入:

4 3 3
0 0 1 1
1 1 3 2
3 2 4 3

输出:

199648871