امیر و مهدی برای گردش به جنگل تصادفی رفته‌اند که درختان این جنگل توجه آنها را جلب می‌کند. آنها برای آشنایی بیشتر با این درختان به اعماق جنگل می‌روند اما بعد از مدتی گم می‌شوند! در عوض آنها به رمز رشد درختان این جنگل پی برده‌اند، الگوریتم ساخت یک درخت $n$ رأسی در جنگل تصادفی به این صورت است:

ابتدا راس $1$ به عنوان ریشه قرار می‌گیرد، سپس در $n - 1$ لحظه بعد، در لحظهٔ $i$ ام، پدر راس $i + 1$ به طور تصادفی با شانس برابر بین رئوس $1$ تا $i$ انتخاب می‌شود و راس $i + 1$ به درخت اضافه می‌شود.

امیر حین تلاش آنها برای خروج از جنگل نقشه‌ای قدیمی پیدا می‌کند که به زبانی باستانی نوشته شده است. امیر شروع به رمزگشایی این زبان می‌کند و می‌فهمد که زیبایی یک درخت از دید یونانیان باستان برابر تعداد دوتایی‌های $(u, v)$ از راس‌‌های درخت است که ارتفاع برابر دارند و $u < v$ است. او بدون دانستن امید ریاضی زیبایی یک درخت $n$ رأسی در جنگل تصادفی نمی‌تواند بخش دوم نقشه را رمزگشایی کند!

تا وقتی که امیر مشغول رمزگشایی دیگر بخش‌های نقشه است، به مهدی کمک کنید جواب مسأله را به پیمانهٔ $M$ بدست آورد و به امیر بدهد تا آنها را از جنگل تصادفی نجات بدهد!

امید ریاضی خواسته شده را می‌توان به صورت $\frac{P}{Q}$ نوشت که $P$ و $Q$ نسبت به هم اولند. در این صورت $P \cdot Q^{-1}$ را به پیمانه‌ی $M$ محاسبه کنید.

تنها سطر ورودی شامل عدد طبیعی $n$، تعداد رئوس درخت، و عدد اول $M$ است.

در تنها سطر خروجی امید ریاضی تعداد جفت راس‌های همطبقه در یک درخت $n$ رأسی تصادفی را به پیمانه $M$ چاپ کنید.

• زیرمسئله اول (۵ نمره): $n \leq 10$
• زیرمسئله دوم (۳۱ نمره): $n \leq 100$
• زیرمسئله سوم (۱۷ نمره): $n \leq 300$
• زیرمسئله چهارم (۴۷ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 5000$
• $10^8 \leq M \leq 10^9$
• $M$ عددی اول است.

4 100000007

16666669

6 998244353

16637409 

10 349101829

213807563 

100 998244853

439156355 

سعی کنید سوالات را با کمترین راهنمایی از بالا به پایین حل کنید.

• سوال قبل
• سوال بعد