Atcoder Educational DP Contest Y - Grid 2

View as PDF

Submit solution


Points: 1.45 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Please read the guidelines before commenting.


There are no comments at the moment.