- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقا فیروز که در طی ماه‌های اخیر عملکرد خیره‌کننده‌ای در کار و نظارتش بر دیگران داشت، توسط شرکت عمرانی سرداد به استخدام درآمد. شرکت عصر دانش‌افزار که در زمینه طراحی و ساخت اپلیکیشن‌های بانکی، مالی و خدمات پرداخت فعالیت دارد، کارهای نرم‌افزاری این شرکت عمرانی را انجام می‌دهد.
در پروژه‌ای که به آقا فیروز داده شده، $n$ روستا وجود دارد که از $1$ تا $n$ شماره‌گذاری شده‌اند. همچنین یک لیست شامل $n - 1$ جاده به آقا فیروز داده شده که هر جاده دوتا از روستاها را به هم وصل می‌کند. تضمین می‌شود پس از احداث جاده‌ها می‌توان با پیمایش تعدادی جاده از هر روستایی به هر روستای دیگری رفت.
همچنین در هر روستا، یک سوله وجود دارد که درون سوله واقع در روستای شماره $i$، دقیقا $i$ تن خاک وجود دارد. همچنین می‌دانیم برای احداث جاده‌ای بین دو روستای $u$ و $v$، باید دقیقا از یکی از این دو روستا، دقیقا ۱ تن خاک برداشت.
حال آقا فیروز که تازه استخدام شده، می‌خواهد خودی نشان دهد. برای همین می‌خواهد تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک مورد نیاز جاده‌ها را بشمارد. اما به‌دلیل اینکه درگیر آنالیز کردن پروژه عمرانی‌اش است، از شما می‌خواهد تا به او در این موضوع کمک کنید.
توجه کنید از آن‌جا که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ خروجی دهید.
ورودی
در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد روستاها می‌باشد.
در $n - 1$ خط بعدی، در هر خط دو عدد $u_i$ و $v_i$ می‌آید و بیانگر این است که جاده‌ای بین دو روستا با شماره‌های $u_i$ و $v_i$ باید احداث شود.
تضمین می‌شود پس از احداث این $n - 1$ جاده، از هر روستایی با پیمایش جاده‌ها می‌توان به هر روستای دیگری رفت. $$1 \le n \le 1\ 000\ 000$$ $$1 \le u_i, v_i \le n$$
خروجی
در تنها خط خروجی، تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک را به باقیمانده $10^9 + 7$ بگویید.
مثال
ورودی نمونه ۱
3
1 2
1 3
خروجی نمونه ۱
3
می‌توان برای احداث جاده‌ی اول، از روستای شماره ۲ خاک برداشت، که در این‌صورت برای احداث جاده دوم می‌توان هم از روستای شماره ۱ و هم از روستای شماره ۳ خاک برداشت. همچنین اگر برای احداث جاده‌ی اول، از روستای شماره ۱ خاک برداریم، چون سوله واقع در روستای ۱، دقیقا یک تن خاک داشت، پس دیگر خاکی در آن باقی نمی‌ماند و مجبوریم از سوله واقع در روستای ۳ خاک برداریم.
پس در کل به ۳ روش می‌توان سوله‌ها را برای برداشتن خاک انتخاب کرد.
ورودی نمونه ۲
4
1 2
2 3
2 4
خروجی نمونه ۲
7
ورودی نمونه ۳
4
2 3
2 1
2 4
خروجی نمونه ۳
7
ارسال پاسخ برای این سؤال