+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- امیر و مهدی برای گردش به جنگل تصادفی رفته‌اند که درختان این جنگل توجه آنها را جلب می‌کند. آن‌ها برای آشنایی بیشتر با این درختان به اعماق جنگل می‌روند اما بعد از مدتی گم می‌شوند! در عوض آن‌ها به رمز رشد درختان این جنگل پی برده‌اند، الگوریتم ساخت یک درخت $n$ رأسی در جنگل تصادفی به این صورت است: ابتدا راس $1$ به عنوان ریشه قرار می‌گیرد، سپس در $n - 1$ لحظه بعد، در لحظه $i$ ام، پدر راس $i + 1$ به طور تصادفی با شانس برابر بین رئوس $1$ تا $i$ انتخاب می شود و راس $i + 1$ به درخت اضافه می‌شود. امیر حین تلاش آن‌ها برای خروج از جنگل نقشه‌ای قدیمی پیدا می‌کند که به زبانی باستانی نوشته شده است. امیر شروع به رمزگشایی این زبان می‌کند و می‌فهمد که زیبایی یک درخت از دید یونانیان باستان برابر تعداد دوتایی‌های $(u,v)$ از راس های درخت است که ارتفاع برابر دارند و $u < v$ است. او بدون دانستن امید ریاضی زیبایی یک درخت $n$ راسی در جنگل تصادفی نمی‌تواند بخش دوم نقشه را رمزگشایی کند! تا وقتی که امیر مشغول رمزگشایی دیگر بخش‌های نقشه است، به مهدی کمک کنید جواب مسأله را به پیمانهٔ $M$ بدست آورد و به امیر بدهد تا آن‌ها را از جنگل تصادفی نجات بدهد! امید ریاضی خواسته شده را می‌توان به صورت $\frac P Q$ که $P$ و $Q$ نسبت به هم اولند. در این صورت $P.Q^{-1}$ را به پیمانه $M$ محاسبه کنید. # ورودی تنها سطر ورودی شامل عدد طبیعی $n$، تعداد رئوس درخت، و عدد اول $M$ است. $$1 \leq n \leq 5000$$ $$10^8 \leq M \leq 10^9$$ # خروجی در تنها سطر خروجی، امید ریاضی تعداد جفت راس های هم‌طبقه در یک درخت $n$ راسی تصادفی را به پیمانه $M$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-----:|:-------:|:----------------------------:| | ۱ | ۵ | $n \leq 10$ | | ۲ | ۳۱ | $n \leq 100$ | | ۳ | ۱۷ | $n \leq 300$ | | ۴ | ۴۷ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 4 100000007 ``` ## خروجی نمونه ۱ ``` 16666669 ``` ## ورودی نمونه ۲ ``` 6 998244353 ``` ## خروجی نمونه ۲ ``` 16637409 ``` ## ورودی نمونه ۳ ``` 10 349101829 ``` ## خروجی نمونه ۳ ``` 213807563 ``` ## ورودی نمونه ۴ ``` 100 998244853 ``` ## خروجی نمونه ۴ ``` 439156355 ```