• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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

در این ارتباط‌ ها، هر جاسوس یک کد دارد که در برقراری ارتباط با دیگر جاسوس‌ها از آن استفاده می کند. (دقت کنید که کد جاسوس $i$ ($1 \leq i \leq n$) می‌تواند $i$ نباشد.) کد جاسوس‌ها یک عدد طبیعی از 1 تا $n$ است و هم‌چنین کد هر دو جاسوسی متفاوت است. به خاطر دلایل نامعلوم، سازمان اطلاعات برای هر جفت جاسوس $(i,j)$ که می‌توانند باهم ارتباط برقرار کنند، مشخص کرده است که کد کدام یک از دو جاسوس باید کوچکتر باشد.

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

ورودی

سطر اول ورودی شامل عدد طبیعی، $n$، تعداد جاسوس‌ها است.

در هر یک از $n-1$ سطر بعدی به ترتیب دو عدد $u$ و $v$ آمده است که به معنای این است که جاسوس $u$ و $v$ می‌توانند باهم ارتباط تلفنی برقرار کنند و هم‌چنین کد جاسوس $u$ باید کمتر از کد جاسوس $v$ باشد. $$1 \leq n \leq 3\ 000$$ $$u \ne v , 1 \leq u,v \leq n$$

خروجی

در تنها سطر خروجی، باقی‌مانده‌ی تعداد روش‌های کدگذاری جاسوس‌ها بر $10^9 + 7$ را چاپ کنید.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

3
1 2
2 3

خروجی نمونه ۱

1

ورودی نمونه ۲

4
1 4
2 4
3 4

خروجی نمونه ۲

6