Cho 1 bảng m*n, trong đó có k ô có vật cản. Đếm số cách đi từ (1,1) đến (m,n) sao cho không đi vào ô có vật cản và từ ô (i,j) chỉ được đi sang 1 trong 2 ô (i+1,j) hoặc (i,j+1).
Input:
Dòng đầu gồm 3 số là kích thước của bảng và số vật cản m,n,k (m,n<=1e5, k<=1000).
k dòng tiếp theo, mỗi dòng ghi toạ độ 1 vật cản.
Output:
Số cách mod 1e9+7.
input | output |
3 3 1 2 2 |
2 |