Busy Beaver có hai thẻ bài được bôi sơn. Anh ấy muốn sơn một đồ thị vô hướng theo cách sau:

• Ban đầu, tất cả các đỉnh đều chưa được sơn. Đầu tiên, Busy Beaver đặt một thẻ lên đỉnh 1 và thẻ kia lên đỉnh 2.
• Sau đó, anh ấy trượt các thẻ dọc theo các cạnh của đồ thị; bất cứ khi nào một đỉnh được thẻ che phủ, đỉnh đó sẽ được sơn. (Lưu ý rằng các đỉnh 1 và 2 ban đầu đã được sơn.)
• Nếu có thể sơn tất cả các đỉnh sao cho hai thẻ không bao giờ được nối với nhau bởi một cạnh tại bất kỳ thời điểm nào trong quá trình, đồ thị đó được gọi là nghệ thuật.

Hãy tìm số lượng đồ thị vô hướng nghệ thuật trên $N$ đỉnh. Vì kết quả có thể rất lớn, hãy xuất ra kết quả theo modulo một số nguyên tố $P$.

Dữ liệu vào

Dòng duy nhất của mỗi bộ test chứa hai số nguyên $N$ và $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$). $P$ là số nguyên tố.

Dữ liệu ra

Xuất ra số lượng đồ thị vô hướng nghệ thuật trên $N$ đỉnh, theo modulo $P$.

Ví dụ

Dữ liệu vào 1

2 799999999

Dữ liệu ra 1

1

Dữ liệu vào 2

3 998244853

Dữ liệu ra 2

2

Dữ liệu vào 3

1984 998244853

Dữ liệu ra 3

424428556

Ghi chú

Trong bộ test đầu tiên, đồ thị với hai đỉnh và không có cạnh nào là đồ thị nghệ thuật duy nhất.

Trong bộ test thứ hai, hai đồ thị đầu tiên dưới đây là nghệ thuật. Đồ thị cuối cùng không phải là nghệ thuật, vì không thể sơn được đỉnh 3.