ICPC
一张纸对应平面上的矩形 [0,n]×[0,m],按整数坐标划分为单位方格。纸上有 k 块墨迹,第 i 块占据矩形 [ai,ci]×[bi,di]。
从 (0,0) 到 (n,m) 的每条单调格点路径由向右一步 (1,0) 和向上一步 (0,1) 组成。在所有这样的路径中等概率选择一条,沿它把纸分开。
求所有墨迹都完整保留在同一侧纸上的概率。路径可以沿墨迹矩形的边界行走,但不能穿过墨迹内部,也不能把不同的墨迹分在两侧。沿纸张外边界、使其中一侧为空的路径也参与随机选择。墨迹矩形可以重叠。
答案对 M=998244353 取模:若真实概率为既约分数 p/q,输出 p⋅q−1modM。本题保证分母模 M 非零。
输入格式
每个文件只有一个用例。第一行三个整数 n,m,k,均满足 1≤n,m,k≤2×105。
接下来 k 行,每行四个整数 ai,bi,ci,di,满足
0≤ai<ci≤n,0≤bi<di≤m.
输出格式
输出一个整数,表示所求概率模 998244353 的值。
样例
输入:
4 3 3
0 0 1 1
1 1 3 2
3 2 4 3
输出:
199648871