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

فرض کنید $k$ تا از راس‌های درخت را علامت‌دار کردیم. سپس گراف کامل $k$ راسی $G$ را تعربف می‌کنیم که راس‌هایش متناظر با راس‌های علامت‌دار درخت هستند، و وزن یال بین راس‌های $v$ و $u$ برابر با فاصله‌ی این دو راس در درخت اصلی می‌باشد. حال امتیاز این درخت علامت‌دار را $MST(G)$ تعریف می‌کنیم.

از آنجایی که آشمز فکر می‌کند سطح این سوال پایین است، جمع امتیاز تمام درخت‌های علامت‌دار، بین هر $2^n$ حالت ممکن را می‌خواهد. در این سوال شما باید پاسخ این سوال را به پیمانه‌ی $10^9 + 7$ محاسبه و چاپ کنید.

در خط اول ورودی عدد طبیعی $n$ تعداد راس‌های درخت می‌آید.

در هر یک از $n - 1$ خط بعدی دو عدد $v$ و $u$ به ترتیب می‌آیند که نشان‌دهنده‌ی یالی بین $v$ و $u$ است.

خروجی برنامه شامل یک خط است که جمع امتیاز تمام $2^n$ درخت علامت‌دار ممکن را به پیمانه‌ی $10^9 + 7$ نشان می‌دهد.

• زیرمسئله اول (۱۵ نمره): $n \leq 22$
• زیرمسئله دوم (۱۵ نمره): به جز یک راس، به هر راس حداکثر دو یال متصل است.
• زیرمسئله سوم (۳۵ نمره): $n \leq 1000$
• زیرمسئله چهارم (۳۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 5000$
• $1 \leq v, u \leq n$
• تضمین می‌شود یال‌ها تشکیل درخت می‌دهند.

• سوال قبل