سپس از هرس کردن درخت در روز قبل، آشمز علاقه‌ی زیادی به درختان پیدا کرده است. او تصمیم می‌گیرد روی درخت $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$ نشان می‌دهد.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 1 2 2 3 | 6 |
| 7 3 1 1 2 3 5 4 5 3 6 6 7 | 496 |