Problem 1049 --撸猫狂魔

1049: 撸猫狂魔

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 165  Solved: 32
[Submit][Status][Web Board][Creator:]

Description

zyyyyy是一个二刺猿。虽然他没有九十八亿,但是他坚信可爱即正义,所以他特别喜欢撸猫。
今天他为了让猫乖乖的被撸带了很多很多猫粮,猫粮被摆成网格图,于是一大群白猫为了吃猫粮也成了网格图。
等它们吃的开心了zyyyyy就开始撸她们。当他撸某只猫的时候,这只猫所在的行和列的猫虽然在吃东西但还是会被吓得变色(白猫变黑猫,黑猫变白猫),而这只猫因为惊吓过度就变了两次色(相当于不变色)。
撸了k次以后zyyyyy心满意足,不过现在他想知道自己闯了多大的祸。。。因为原来这些猫都是白的,现在有很多变成黑的了。定义整个网格图的黑色值等于所有行的黑色值相乘,一行的黑色值是这行黑猫的个数。不过黑色值可能太大了,为了避免他倍受打击我们还是告诉他黑色值模1000000007的值吧。。。

Input

第一行三个整数,n,m,k。表示行数,列数,撸猫次数。
接着k行每行两个整数,x,y。表示这次撸的是x行y列的猫 (可以重复撸)
n,m <= 1000
k <= 500000
1<=x<=n
1<=y<=m

Output

一个整数,表示黑色值模1000000007的值。

Sample Input

5 4 2
3 3
3 2

Sample Output

32

HINT

Source

[Submit][Status]