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

خزانهٔ کمیته از $n$ اتاق تشکیل شده که میان بعضی از آنها یک مسیر مستقیم وجود دارد. گراف اتاق‌ها به مانند یک درخت است. در $k$ اتاق از این $n$ اتاق یک نگهبان مستقر شده و گوش به زنگ خطر می باشد. در هر کدام از اتاق‌های دیگر یک گاوصندوق وجود دارد که بعضی خالی و بعضی پر پول است. مهدی به اتاقی خوب می گوید اگر دارای گاوصندوق باشد و گاوصندوق آن پر پول باشد.کمیته برای بالا بردن امنیت خزانه سیاست عجیبی در پیش گرفته؛ کمیته تنها در اتاق‌هایی پول قرار می دهد که در مسیر بین دو نگهبان آمده باشد. به بیانی دیگر هر اتاق خوب است اگر و تنها اگر داری نگهبان نباشد و در میانهٔ مسیر بین دو نگهبان باشد.

اما مهدی که نمی خواهد دزدی کند! یعنی نیازی نیست که نگران نگهبان‌ها باشد؛ او صرفا می‌خواهد مانند تمامی هم‌صنفان شریف خود تنها کمی اختلاس کند و برای این کار نیازمند دست و پا کردن مسئولیتی برای خود در خزانه است. به همین سبب به عمو رو می زند تا به او کمک کند. عمو که در ابتدا راضی نمی شد پس از تلاش های شبانه روزی مهدی پذیرفت که به او کمک کند. اما به یک شرط! عمو که عاشق المپیاد بود سوالی برای مهدی طراحی کرد و به او گفت اگر این سوال را حل کنی به تو کمک خواهم کرد.

سوال عمو به این شرح است:

«مجموعهٔ خوب را معادل با مجموعهٔ همهٔ اتاق‌های خوب تعریف میکنیم؛ یعنی مجموعه‌‌ٔ خوب زیرمجموعه ای از کل اتاق‌هاست که شامل همهٔ اتاق‌های خوب می شود. به ازای تمامی ${n \choose k}$ حالت تعیین اتاق‌های دارای نگهبان چند مجموعهٔ خوب متفاوت داریم؟»

مهدی که ذهنش درگیر مراحل بعدی اختلاس است زمان فکر کردن به سوال عمو را ندارد، برای همین از شما کمک خواسته تا به سوالش پاسخ دهید و به او در انجام امر خطیر اختلاس یاری رسانید.

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

سطر اول ورودی شامل دو عدد طبیعی، $n$ ، تعداد اتاق‌ها و $k$ ، تعداد نگهبان‌ها است.

در هر یک از $n-1$ سطر بعدی دو عدد $u$ و $v$ آمده است که نشان دهندهٔ مسیری مستقیم بین دو اتاق $u$ و $v$ است.

در تنها سطر خروجی جواب مسئله را به پیمانه $10^9 + 7$ خروجی دهید.

• زیرمسئله اول (۹ نمره): $1 \leq n \leq 20$.
• زیرمسئله دوم (۱۱ نمره): درخت ورودی مسیر است.
• زیرمسئله سوم (۳۷ نمره): $1 \leq n \leq 300$.
• زیرمسئله چهارم (۴۳ نمره): بدون محدودیت اضافی

• $1 \leq k \leq n \leq 6000$
• $1 \leq u, v \leq n$

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

• سوال بعد