Có một lưới ô vuông gồm ~H~ hàng và ~W~ cột. Toạ độ ~(i, j)~ biểu thị cho ô vuông ở hàng ~i~ từ trên xuống và cột ~j~ từ trái sang. Trong lưới ô vuông có ~N~ ô ~(r_1,c_1), (r_2,c_2), ...(r_n,c_n)~ là những ô có chướng ngại vật, ngoài những ô này ra tất cả các ô còn lại là các ô trống có thể đi được. Lưới ô vuông đảm bảo rằng ô ~(1,1)~ và ô ~(H, W)~ là ô trống.
Taro sẽ bắt đầu ở ô ~(1,1)~ và đi đến ô ~(H, W)~ bằng cách di chuyển liên tục sang phải hoặc xuống dưới tới các ô trống liền kề.
Hãy tìm số cách mà Taro có thể đi từ ô ~(1,1)~ đến ô ~(H, W)~ và in kết quả dưới dạng modulo của ~10^9 + 7~
Input
- Dòng đầu chứa ba số nguyên ~H, W~ và ~N~ lần lượt là số hàng, số cột và số ô có chướng ngại vật.
- ~N~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~r_i~, ~c_i~ là toạ độ của chướng ngại vật ~i~.
Giới hạn:
- ~2 \le H, W \le 10^5~
- ~1 \le N \le 3000~
- ~1 \le r_i \le H~
- ~1 \le c_i \le W~
- Tất cả các ô ~(r_i, c_i)~ là đôi một phân biệt.
Output
Số cách đi từ ô ~(1,1)~ đến ô ~(H, W)~ dưới dạng modulo của ~10^9 + 7~
Sample 1
Input
3 4 2
2 2
1 4
Output
3
Có ~3~ cách đi như hình sau:
Sample 2
Input
5 2 2
2 1
4 2
Output
0
Không có đường đi nào.
Sample 3
Input
5 5 4
3 1
3 5
1 3
5 3
Output
24
Sample 4
Input
100000 100000 1
50000 50000
Output
123445622
Note
Hãy đảm bảo kết quả in ra dưới dạng modulo của ~10^9 + 7~.
Comments