Số đường đi

View as PDF

Submit solution

Points: 400 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho lưới ô vuông kích thước ~n× m~, ô (~1, 1~) ở góc dưới trái, ô (~n,m~) – trên phải. Có ~k~ ô chứa chướng ngại vật, ô thứ ~i~ ở tọa độ (~x_i, y_i~), ~1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, i = 1 ÷ k~, Không có chướng ngại vật ở ô (~1, 1~) và (~n, m~).

Rô bốt xuất phát từ ô (~1, 1~), ở mỗi bước được chuyển sang ô kề cạnh bên phải hoặc bên trên nếu ô tới không chứa chướng ngại vật.

Hãy xác định số lượng đường rô bốt có thể đi từ ô (~1, 1~) đến ô (~n, m~) và đưa ra số lượng theo mô đun ~p~, trong đó ~p~ – số nguyên tố.

Dữ liệu

  • Dòng đầu tiên chứa 4 số nguyên ~n, m, k, p~ (~1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ 100,2 \times max{m,n} < p < 2 × 10^9~),
  • Nếu ~k > 0~, dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa 2 số nguyên ~x_i, y_i~ (~1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m~).

Kết quả

  • Đưa ra một số nguyên không âm – số lượng đường tìm được theo mô đun ~p~.

Sample input

5 6 3 101
2 2
3 5
4 2

Sample output

25

Nguồn: Thầy Tùng


View comments (1)

Comments


  • 3
    volantuan0908  commented on 9:29 p.m. 28 jul, 2022

    Bài này rất hay, nhưng em chưa biết làm. Các anh/ chị/ thầy/ cô đã AC có thể viết Solution cho em tham khảo được không ạ? Em cảm ơn.