JOI vừa chơi với các bạn bằng những con thú linh vật. Các bạn đã về và giờ là lúc dọn dẹp.

JOI có \(R\times C\) con thú và dùng một bảng hình chữ nhật gồm \(R\) hàng, \(C\) cột để cất chúng. Mỗi ô chứa một con thú. Ô ở hàng \(A\) tính từ trên xuống và cột \(B\) tính từ trái sang được ký hiệu là \((A,B)\).

Ban đầu đã có \(N\) con thú được đặt vào các ô, và còn ít nhất một ô trống. JOI đặt lần lượt từng con thú còn lại vào một ô trống cho đến khi lấp đầy bảng. Các con thú không được phân biệt theo loại; một cách đặt được xác định bởi thứ tự các ô được lấp đầy.

Sau mỗi lần đặt thêm một con thú, nếu toàn bộ các ô có thú tạo thành đúng một hình chữ nhật thì JOI cảm thấy vui một lần. Nếu trạng thái ban đầu đã là một hình chữ nhật thì trạng thái đó không được tính.

Cụ thể, toàn bộ các ô có thú tạo thành một hình chữ nhật khi tồn tại bốn số nguyên \(r_1,r_2,c_1,c_2\) thỏa mãn \(1\le r_1\le r_2\le R\) và \(1\le c_1\le c_2\le C\), sao cho mọi ô \((i,j)\) với \(r_1\le i\le r_2\) và \(c_1\le j\le c_2\) đều có thú, còn tất cả ô khác đều không có thú.

JOI càng có nhiều lần cảm thấy vui thì tối nay càng ngủ ngon. Có bao nhiêu cách đặt các con thú để số lần cảm thấy vui đạt giá trị lớn nhất?

Yêu cầu

Cho kích thước bảng và vị trí những con thú đã được đặt, hãy đếm số thứ tự đặt các con thú còn lại làm số lần cảm thấy vui lớn nhất. Tính kết quả theo modulo \(1000000007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(R,C\), là số hàng và số cột của bảng.
• Dòng thứ hai chứa số nguyên \(N\), là số con thú đã được đặt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), cho biết ô \((A_i,B_i)\) ban đầu đã có thú. Các cặp tọa độ này đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số cách đặt đạt số lần cảm thấy vui lớn nhất, lấy phần dư khi chia cho \(1000000007\).

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(2\le R,C\le3000\).
• \(1\le N\le100000\) và \(N<R\times C\).
• \(1\le A_i\le R\) và \(1\le B_i\le C\).
• Các ô ban đầu có thú đôi một khác nhau.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(R,C\le3\).
• Nhóm 2 (30 điểm): \(R,C\le50\).
• Nhóm 3 (60 điểm): Không có ràng buộc bổ sung.

2 3
2
1 2
2 2

8

Trong sáu ô, hai ô \((1,2)\) và \((2,2)\) ban đầu đã có thú. Số lần cảm thấy vui lớn nhất là \(2\). Có đúng tám thứ tự đặt đạt giá trị này:

Trong mỗi cách, sau lần đặt thứ \(2\), các ô có thú tạo thành hình chữ nhật \(2\times2\); sau lần đặt thứ \(4\), chúng tạo thành hình chữ nhật \(2\times3\). Vì vậy JOI cảm thấy vui tổng cộng hai lần.

3 3
2
1 1
3 3

5040

Dù đặt theo thứ tự nào, JOI cũng chỉ cảm thấy vui một lần, khi toàn bộ bảng được lấp đầy. Vì còn \(7\) ô trống nên có \(7!=5040\) cách đặt.