Ở vương quốc JOI, mỗi năm có một lễ hội toàn quốc. Trong thời gian diễn ra lễ hội có tổng cộng \(N\) sự kiện, với lịch trình đã được ấn định. Lịch của \(N\) sự kiện được mô tả bởi hai dãy \(a,b\) có độ dài \(N\), thỏa mãn:

• Mỗi số nguyên từ \(1\) đến \(2N\) xuất hiện trong dãy \(a\) hoặc dãy \(b\).
• \(a_i<b_i\) với \(1\le i\le N\).
• \(a_i<a_{i+1}\) với \(1\le i\le N-1\).

Sự kiện thứ \(i\) bắt đầu sau \(a_i\) phút kể từ khi lễ hội bắt đầu và kết thúc sau \(b_i\) phút kể từ khi lễ hội bắt đầu.

Người tham gia có thể chọn bất kỳ sự kiện nào, nhưng không được tham gia hai sự kiện có thời gian chồng lấn. Lưu ý rằng tất cả các thời điểm bắt đầu và kết thúc của các sự kiện đều khác nhau.

JOI-kun muốn tham gia càng nhiều sự kiện càng tốt. Cho đến năm ngoái, cậu dùng máy tính để chọn các sự kiện theo thuật toán sau:

Với \(i=1,2,\ldots,N\), lần lượt thực hiện:

• Nếu thời gian của sự kiện thứ \(i\) không chồng lấn với thời gian của bất kỳ sự kiện nào đã chọn tham gia trước đó, chọn tham gia sự kiện thứ \(i\).
• Nếu không, không tham gia sự kiện thứ \(i\).

Sau khi học khoa học máy tính, JOI-kun nhận ra thuật toán trên không phải lúc nào cũng cho số sự kiện tham gia lớn nhất. Từ năm nay, cậu sẽ dùng một thuật toán cải tiến, luôn chọn được số sự kiện lớn nhất có thể tham gia.

JOI-kun muốn biết có bao nhiêu trường hợp mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn thuật toán cũ.

Cho số nguyên \(N\) và một số nguyên tố lớn \(P\), hãy đếm số cặp dãy \(a,b\) mô tả lịch của \(N\) sự kiện mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn. Vì kết quả có thể rất lớn, hãy xuất phần dư của kết quả khi chia cho \(P\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N P

Dữ liệu ra

Xuất một dòng ra đầu ra chuẩn chứa phần dư khi chia cho \(P\) của số cặp dãy \(a,b\) mô tả lịch của \(N\) sự kiện mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn thuật toán cũ.

Ràng buộc

• \(1\le N\le 20\,000\).
• \(10^8<P<10^9\).
• \(P\) là số nguyên tố.
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(5\) điểm: \(N\le 5\).
2. \(5\) điểm: \(N\le 8\).
3. \(27\) điểm: \(N\le 30\).
4. \(14\) điểm: \(N\le 300\).
5. \(36\) điểm: \(N\le 3\,000\).
6. \(13\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 100000007

2

4 100000007

28

15 999999937

935834920

Nguồn

JOI 2022/2023 Spring Training, Contest 1, bài Festivals in JOI Kingdom 2, tác giả 渡邉雄斗.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.