آشمز در روز درخت کاری سال گذشته، که نزدیک آزمون های انتخابی تیم بود، یک درخت جهت‌دار ! در حیاط باشگاه دانش‌پژوهان جوان کاشت. در این یک سال، درخت رشد کرده و دارای $n$ راس شده است.

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

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

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

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

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

• زیرمسئله اول (۷ نمره): $n \leq 18$
• زیرمسئله دوم (۱۴ نمره): به هر راس حداکثر دو یال متصل است.
• زیرمسئله سوم (۴۲ نمره): $n \leq 100$
• زیرمسئله چهارم (۳۷ نمره): بدون محدودیت اضافی

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

• سوال قبل
• سوال بعد