- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
- آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران
مهدی برای پر کردن اوقات فراغت تابستانی خود در دوره چگونه مختلس باشیم شرکت کرده است. اکنون پس از گذشت حدود دو ماه دوره به پایان رسیده و زمان آزمون فرا رسیده! استاد این دوره، آقا محمودرضا که به واسطهٔ رابطهٔ فامیلی که با مهدی دارد در او استعداد شایانی می‌دید برای او آزمون متفاوت و سختی در نظر گرفته است. مهدی برای گرفتن مدرک این دوره می‌بایست تمامی بودجهٔ کمیته را بالا بکشد! کمیته که بودجهٔ بسیار زیادی دارد برای امنیت هر چه تمام‌تر، بودجهٔ خود را در گاوصندوق‌هایی در خزانه نگهداری می‌کند.
خزانهٔ کمیته از $n$ اتاق تشکیل شده که میان بعضی از آن‌ها یک مسیر مستقیم وجود دارد. گراف اتاق‌ها به مانند یک درخت است. در $k$ اتاق از این $n$ اتاق یک نگهبان مستقر شده و گوش به زنگ خطر می‌باشد. در هر کدام از اتاق‌های دیگر یک گاوصندوق وجود دارد که بعضی خالی و بعضی پر پول است. مهدی به اتاقی خوب می‌گوید اگر دارای گاوصندوق باشد و گاوصندوق آن پر پول باشد.کمیته برای بالا بردن امنیت خزانه سیاست عجیبی در پیش گرفته؛ کمیته تنها در اتاق‌هایی پول قرار می‌دهد که در مسیر بین دو نگهبان آمده باشد. به بیانی دیگر هر اتاق خوب است اگر و تنها اگر داری نگهبان نباشد و در میانهٔ مسیر بین دو نگهبان باشد.
اما مهدی که نمی‌خواهد دزدی کند! یعنی نیازی نیست که نگران نگهبان‌ها باشد؛ او صرفا می‌خواهد مانند تمامی هم‌صنفان شریف خود تنها کمی اختلاس کند و برای این کار نیازمند دست و پا کردن مسئولیتی برای خود در خزانه است. به همین سبب به عمو رو می زند تا به او کمک کند. عمو که در ابتدا راضی نمی شد پس از تلاش‌های شبانه روزی مهدی پذیرفت که به او کمک کند. اما به یک شرط! عمو که عاشق المپیاد بود سوالی برای مهدی طراحی کرد و به او گفت اگر این سوال را حل کنی به تو کمک خواهم کرد.
سوال عمو به این شرح است:
«مجموعهٔ خوب را معادل با مجموعهٔ همهٔ اتاق‌های خوب تعریف می‌کنیم؛ یعنی مجموعهٔ خوب زیرمجموعه ای از کل اتاق‌هاست که شامل همهٔ اتاق‌های خوب می‌شود. به ازای تمامی ${n} \choose {k}$ حالت تعیین اتاق‌های دارای نگهبان چند مجموعهٔ خوب متفاوت داریم؟»
مهدی که ذهنش درگیر مراحل بعدی اختلاس است زمان فکر کردن به سوال عمو را ندارد، برای همین از شما کمک خواسته تا به سوالش پاسخ دهید و به او در انجام امر خطیر اختلاس یاری رسانید.
بخاطر اینکه عمو قلب بسیار مهربانی دارد کافی است باقی‌ماندهٔ جواب را به پیمانهٔ $10 ^ 9 + 7$ خروجی دهید.
ورودی
سطر اول ورودی، شامل دو عدد طبیعی، $n$ تعداد اتاق‌ها و $k$ تعداد نگهبان‌ها است. $$1 \leq k \leq n \leq 6000$$
در هر یک از $n-1$ سطر بعدی دو عدد $u$ و $v$ آمده است که نشان دهندۀ مسیری مستقیم بین دو اتاق $u$ و $v$ است.
$$1 \leq u , v \leq n$$
خروجی
در تنها سطر خروجی جواب مسئله را به پیمانه $10 ^ 9 + 7$ خروجی دهید.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۹ | $1 \leq n \leq 20$ |
| ۲ | ۱۱ | درخت ورودی مسیر است |
| ۳ | ۳۷ | $1 \leq n \leq 300$ |
| ۴ | ۴۳ | بدون محدودیت اضافی |
مثال‌ها
ورودی نمونه ۱
5 1
1 2
2 4
3 5
3 2
خروجی نمونه ۱
1
ورودی نمونه ۲
7 3
1 4
4 5
5 6
5 7
7 3
7 2
خروجی نمونه ۲
8
ارسال پاسخ برای این سؤال