Một nhóm nhân viên khai mỏ có dự định tiến vào một hầm mỏ dài và rất hẹp. Vì rất hẹp và dài, nên chỉ người vào cuối cùng mới có thể rời khỏi hầm mỏ. Ban đầu, hầm mỏ trống. Ở cửa hầm mỏ, chúng ta ghi lại thời gian một ai đó vào và ra hầm mỏ. Mỗi người thợ mỏ không được ở trong hầm mỏ quá đơn vị thời gian. Hãy đếm xem có bao nhiêu tình huống khác nhau có thể xảy ra. Hai tình huống được xem là khác nhau, nếu tồn tại một thời điểm nào đó mà trong tình huống này, người có trong hầm mỏ, trong tình huống khác, người không có trong hầm mỏ. Các công nhân khai mỏ được đánh số từ đến . Công nhân khai mỏ thứ không được vào hầm mỏ trước công nhân khai mỏ thứ (Công nhân là người vào đầu tiên).
Dữ liệu vào:
Dòng đầu ghi hai số nguyên và , trong đó và
Dòng thứ hai ghi số nguyên dương là thời điểm (tính từ đầu ngày) có một người thợ mỏ vào hoặc ra hầm mỏ
Dữ liệu ra:
In ra kết quả theo modulo
Ví dụ:
Dữ liệu vào:
3 6
1 2 3 7 9 10
Dữ liệu ra:
2
Giải thích:
Có 3 người thợ mỏ. Giả sử người đầu vào mỏ ở thời điểm :
Nếu rời mỏ ở thời điểm , thì người sẽ vào mỏ ở thời điểm . Do không được ở trong mỏ ở quá , nên không thể rời mỏ ở thời điểm . không thể rời mỏ ở thời điểm vì khi đó ở thời điểm có người thứ đi vào và chặn lỗi ra. Do đó chỉ có thể rời ở thời điểm . Và người thứ đến và đi ở thời điểm , . Đây là tình huống .
Nếu rời mỏ ở thời điểm , thì và là hai thời điểm đến và đi của hai người khác nhau, đây là tình huống .
không thể rời mỏ ở thời điểm (vì thời điểm có người đến và phong tỏa không cho ra).
