CSES - Grid Paths | Đường đi trên lưới
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một lưới \(n \times n\) với ô vuông trên cùng bên trái là \((1,1)\) và ô vuông dưới cùng bên phải là \((n, n)\).
Nhiệm vụ của bạn là di chuyển từ ô trên cùng bên trái sang ô dưới cùng bên phải. Trên mỗi bước, bạn có thể di chuyển một ô sang phải hoặc xuống dưới. Ngoài ra, có \(m\) bẫy trong lưới. Bạn không thể di chuyển đến một ô có bẫy.
Tổng số cách có thể di chuyển được là bao nhiêu?
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): kích thước mảng và số lượng bẫy.
- \(m\) dòng tiếp theo mô tả các bẫy. Mỗi dòng chứa hai số nguyên \(y\) và \(x\): vị trí của một cái bẫy.
- Dữ liệu đảm bảo không có bẫy trong hình vuông trên cùng bên trái và dưới cùng bên phải.
Output
- Một dòng duy nhất chứa tổng số cách di chuyển sau khi modulo cho \(10^9 + 7\).
Constraints
- \(1 \leq n \leq 10^6\)
- \(1 \leq m \leq 1000\)
- \(1 \leq y, x \leq n\)
Example
Sample input
3 1
2 2
Sample output
2
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.