دوستی (Friendship)

به تازگی تمام آرایه‌های $n$ عضوی که اعضای آن‌ها اعداد طبیعی از 1 تا $m$ هستند وارد شهر اعداد شده‌اند. در شهر اعداد دو قانون وجود دارد: برابری و دوستی.

آرایه‌ها که در شهر اعداد زندگی می‌کنند، دنبال برقراری هر دو قانون هستند. دو آرایه با اندازه برابر با هم دوست هستند اگر و تنها اگر جمع اعضای متناظر آن‌ها تشکیل یک آرایه اکیداً صعودی دهند. به بیان دیگر دو آرایه $a_1, a_2, \dots, a_n$ و $b_1, b_2, \dots,b_n$ با هم دوست هستند اگر و تنها اگر به ازای هر $1 \leq i \leq n - 1$ شرط $a_i + b_i < a_{i+1} + b_{i + 1}$ برقرار باشد (دقت کنید که طبق تعریف یک آرایه می‌تواند با خودش هم دوست باشد).

حال رئیس شهر اعداد یعنی $42$، از شما خواسته تا تعداد آرایه‌هایی که در شهر اعداد زندگی ‌می‌کنند و حداقل یک دوست در شهر دارند را حساب کنید. از آن‌جایی که ممکن است این عدد خیلی بزرگ باشد کافیست تنها باقی‌مانده تقسیم این عدد بر عدد اول $p$ را به دست آورید.

دقت کنید که هم خود آرایه و هم دوست آن باید در شهر باشند، یعنی $n$ عضوی باشند و اعضای آن‌ها هم اعداد طبیعی بین $1$ تا $m$ باشند.

تنها خط ورودی شامل 3 عدد $n$، $m$، $p$ است که به ترتیب برابر با اندازه آرایه‌ها، حداکثر مقدار اعضای آرایه‌ها و عدد اول $p$ است.

در تنها خط خروجی باید باقی‌مانده تقسیم تعداد آرایه‌هایی در شهر که حداقل یک دوست در شهر دارند را بر $p$ خروجی دهید.

• زیرمسئله اول (۴ نمره): $n \leq 4, m \leq 4$
• زیرمسئله دوم (۸ نمره): $n \leq 8, m \leq 8$
• زیرمسئله سوم (۱۶ نمره): $n \leq 2000, m \leq 2000$
• زیرمسئله چهارم (۱۱ نمره): $n = 2m - 1$
• زیرمسئله پنجم (۶۱ نمره): بدون محدودیت اضافی

• $1 \leq n , m \leq 10^6$
• $10^8 \leq p\leq10^9$
• $p$ عددی اول است.

در ورودی نمونه اول، تنها آرایه‌ای که هیچ دوستی ندارد آرایۀ $[3 , 1]$ است.