矩阵计数
题号:NC15363
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

输入

复制
3 3 1
2 3

输出

复制
24

备注:

1 ≤ n,m ≤ 109
0 ≤ C ≤ 5000