Alice đang thử nghiệm khả năng tìm đường của một robot trên lưới ô vuông kích thước m × n.
Hàng đánh số từ 1 đến m (từ trên xuống), cột đánh số từ 1 đến n (từ trái sang phải). Ô giao giữa hàng i và cột j là ô (i, j).
Trên lưới có k ô cấm (x1, y1), (x2, y2), …, (xk, yk) — robot không thể di chuyển vào các ô này. Các ô còn lại là ô tự do. Robot xuất phát tại ô (1,1) và cần đến ô (m,n). Mỗi bước robot chỉ được đi sang ô kề bên phải hoặc ô kề bên dưới, và hai ô (1,1) và (m,n) đều là ô tự do. Alice muốn đếm số đường đi thỏa mãn điều kiện trên.
Cho m, n và vị trí k ô cấm, hãy tính số đường đi từ (1,1) đến (m,n) đi theo quy tắc (chỉ phải hoặc xuống) mà không đi qua ô cấm.
m, n, k (m, n, k ≤ 10^5).t (1 ≤ t ≤ k) của k dòng sau: hai số nguyên x_t, y_t (1 ≤ x_t ≤ min(m,1000); 1 ≤ y_t ≤ min(n,1000)).In ra một số — phần dư (mod 10^9 + 7) của số đường đi hợp lệ.
Ví dụ:
Đầu vào:
4 5 5
2 2
2 3
2 4
4 2
4 3
Đầu ra:
3
Đầu vào:
3 4 1
3 1
Đầu ra:
9
Đầu vào:
3 3 1
2 2
Đầu ra:
2
Đầu vào:
3 3 0
Đầu ra:
6
Đầu vào:
1 1 0
Đầu ra:
1
Đầu vào:
3 4 2
2 2
2 3
Đầu ra:
2
Đầu vào:
1 5 0
Đầu ra:
1
Đầu vào:
5 5 3
2 3
3 4
4 2
Đầu ra:
12
Đầu vào:
4 4 5
1 3
2 1
2 2
3 2
4 1
Đầu ra:
0
Đang tải editor...