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