Bật dãy máy tính

Có $n$ máy tính xếp thành một hàng, đánh số từ $1$ đến $n$. Ban đầu tất cả đều đang tắt, và bạn muốn bật tất cả chúng.

Bạn bật các máy bằng tay, mỗi lần một máy. Tại bất kỳ thời điểm nào, nếu máy $i-1$ và máy $i+1$ đều đang bật thì máy $i$ (với $2\le i\le n-1$) sẽ tự động bật nếu nó chưa bật. Bạn không được bật bằng tay một máy đã tự động bật.

Nếu chỉ xét dãy các máy được bật bằng tay, hỏi có bao nhiêu cách để bật hết tất cả các máy? Hai dãy được coi là khác nhau nếu tập hợp các máy được bật bằng tay khác nhau, hoặc thứ tự bật bằng tay khác nhau.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho $M$.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $n$ và $M$: số lượng máy tính và số chia lấy dư.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách bật tất cả các máy tính, lấy phần dư khi chia cho $M$.

Ràng buộc

• $3\le n\le 400$
• ${10}^8\le M\le {10}^9$, và $M$ là số nguyên tố

Ví dụ