Đếm Đường Đi Với Tối Đa K Lần Rẽ
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Trên lưới $N \times M$, bạn xuất phát tại $(1, 1)$ và đi tới $(N, M)$, mỗi bước chỉ được đi sang phải hoặc xuống dưới. Một đường đi được gọi là hợp lệ nếu số lần đổi hướng (từ đi phải sang đi xuống hoặc ngược lại) không vượt quá $K$. Hãy đếm số đường đi hợp lệ theo modulo $10^9 + 7$.
Dữ liệu vào
- Một dòng duy nhất chứa ba số nguyên $N, M, K$ $(1 \le N, M \le 200, 0 \le K \le 200)$.
Dữ liệu ra
- In ra số đường đi hợp lệ theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 | 2 |
| 3 3 2 | 4 |
Giới hạn
- $1 \le N, M \le 200$
- $0 \le K \le 200$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion