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

مقدار عصبانیت اختاپوس از دست پاتریک برابر ضرب اندازه‌ی مولفه‌های همبند موجود در جنگل نهایی است؛ به عبارت دیگر، اگر جنگل ایجاد شده $k$ مولفه داشته باشد و اندازه‌ی مولفه‌ی $i$اُم برابر $s_i$ باشد، مقدار عصبانیت اختاپوس برابر $\prod_{i=1}^{k} s_i$ خواهد بود.

باب اسفنجی که از دور به این ماجرا نگاه می‌کند سوالی برای سرگرمی خود طرح می‌کند؛ حاصل جمع مقدار عصبانیت اختاپوس به ازای تمام $2^{n-1}$ حالتی که پاتریک می‌تواند یک زیرمجموعه از یال‌های درخت اختاپوس را قیچی کند چقدر است؟

از آنجایی که این مقدار می‌تواند بزرگ باشد و حافظه‌ی باب‌ اسفنجی توانایی محاسبه‌ی مقادیر بزرگ را ندارد، باقی‌مانده‌ی این مقدار بر $10^9 + 7$ را به باب‌ اسفنجی اطلاع دهید.

خط اول شامل عدد $n$ است که نشان‌دهنده‌ی تعداد راس‌های درخت اختاپوس است.

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

تضمین می‌شود که گراف ورودی درخت است.

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

• زیرمسئله اول (۱۰ نمره): $n \leq 20$
• زیرمسئله دوم (۱۶ نمره): $n \leq 500$
• زیرمسئله سوم (۱۱ نمره): $n \leq 5000$
• زیرمسئله چهارم (۱۷ نمره): درخت ورودی مسیر است
• زیرمسئله پنجم (۴۶ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 10^6$

در مثال اول، در حالتی که هیچ یالی حذف نشود عصبانیت اختاپوس برابر $4$ است. اگر یک یال حذف شود، در دو حالت برابر $3$ و در یک حالت برابر $4$ است. هنگامی که دو یال حذف شود، در هر سه حالت عصبانیت اختاپوس برابر $2$ است. در حالتی که هر سه یال حذف شوند نیز عصبانیت اختاپوس برابر $1$ است؛ در نتیجه جواب نهایی برابر $4+(2\times3)+4+(3\times2)+1=21$ است.