5819 - 2025 普及第十二轮第三题:矩阵统计

给一个n行m列的01矩阵,其中C个格子是1,其余全是0。求有多少全0的子矩阵。 答案对10^9 + 7取模。

输入

第一行三个数,分别表示n,m,C。 接下来C行,每行两个数x,y(1 <= x <= n, 1 <= y <= m),表示为1的格子,保证互不相同

输出

仅一行一个数,表示答案。

样例

输入

3 3 1
2 3

输出

24

提示

1 ≤ n,m ≤ 10^9 0 ≤ C ≤ 5000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题