====== جنگل تصادفی (Random Jungle) ======

امیر و مهدی برای گردش به جنگل تصادفی رفته‌اند که درختان این جنگل توجه آنها را جلب می‌کند.
آنها برای آشنایی بیشتر با این درختان به اعماق جنگل می‌روند اما بعد از مدتی گم می‌شوند!
در عوض آنها به رمز رشد درختان این جنگل پی برده‌اند،
الگوریتم ساخت یک درخت 
$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$ عددی اول است.

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
| <code>
4 100000007
</code> | <code>
16666669
</code>|
| <code>
6 998244353
</code> | <code>
16637409 </code>|
| <code>
10 349101829
</code> | <code>
213807563 </code>|
| <code>
100 998244853
</code> | <code>
439156355 </code>|
</WRAP>

  * [[سوال ۱|سوال قبل]]
  * [[سوال ۳|سوال بعد]]