کشور ایتالیا شامل $n$ کشور و $n-1$ جاده‌ی یک طرفه است که جاده‌ها با صرف نظر از جهت‌شان کشور را همبند می‌کنند. کشور ایتالیا در جهت جذب توریست قانون عجیبی را وضع کرده است! اگر شما از جاده‌ای در جهت درست آن استفاده کنید، دولت یک واحد پول به شما می‌دهد. اما اگر در جهت مخالف استفاده کنید، جریمه می‌شوید و باید یک واحد پول پرداخت کنید. حال فرض کنید که شما می‌خواهید در یک سفر تابستانه به آنجا بروید و علاوه بر اینکه از سفرتان لذت ببرید، یک پولی هم به جیب بزنید! زیبایی ایتالیا را تعریف می‌کنیم بیشینه مقدار پولی که می‌توان در یک سفر از آن کسب کرد. یعنی از یک شهر دلخواه شروع کنیم، و طی دنباله حرکاتی دلخواه به شهر دلخواهی برسیم. می‌توان نشان داد زیبایی کشور عددی محدود است و بی‌نهایت نمی‌شود.

در این سوال شما در هر بخش جاده‌های ایتالیا را می‌دانید اما جهت‌شان را نه. برای همین باید مجموع زیبایی ایتالیا را به ازای هر $2^{n-1}$ حالت از جهت‌دهی جاده‌ها محاسبه کنید.

ورودی

در هر بخش کشور ایتالیا به صورت یک درخت توصیف می‌شود. در بعضی از بخش‌ها از اصطلاح درخت بیتی استفاده شده است که تعریفش مطابق زیر است:

• به ازای هر عدد طبیعی $x$ تابع $f(x)$ را تعریف می‌کنیم $x$ منهای تعداد بیت‌های یک خودش در مبنای دو. برای مثال $f(5)=5-2=3$ می‌باشد. منظور از درخت بیتی درختی است که یال $i$ امش بین راس‌های $i+1$ و $f(i+1)$ می‌باشد.

برای مثال درخت بیتی ۱۰ راسی به شکل زیر است:

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$1$- الف ($30$ نمره) : در حالتی که ایتالیا درخت بیتی ۱۰ راسی باشد، جواب به پیمانه‌ی $\Delta$ چقدر است؟

$1$- ب ($35$ نمره) : در حالتی که ایتالیا مسیر $5\cdot10^3$ راسی باشد، جواب به پیمانه‌ی $\Delta$ چقدر است؟

$1$- ج ($35$ نمره) : در حالتی که ایتالیا درخت بیتی $5\cdot10^3$ راسی باشد، جواب به پیمانه‌ی $\Delta$ چقدر است؟ توجه کنید که درخت بیتی تاثیری در راه حل ندارد و هدف حل سوال برای هر درختی است.