• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

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

خزانهٔ کمیته از $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$ خروجی دهید.

زیرمسئله‌ها🔗

مثال‌ها🔗

ورودی نمونه ۱🔗

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

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

آقای دنباله‌نژاد که کل عمرش را صرف تحلیل دنباله‌ها کرده، باور دارد می‌توان با استفاده از دنباله‌ها وقوع حوادث ناگوار را پیشبینی کرد. برای این کار آقای دنباله‌نژاد هر جفت از اعداد دنباله را تحلیل می‌کند و سپس میزان نحسی دنباله را محاسبه می‌کند.

آقای دنباله‌نژاد از نابجایی و همچنین از عدد $k$ متنفر است. به همین دلیل به زوج $i$‌ و $j$ که $i<j$ یک جفت شوم می‌گوید اگر $a_i > a_j$ برقرار باشد. به آن بدشگون می‌گوید اگر $a_i \oplus a_j > k$ باشد (نماد $\oplus$ نشان‌دهندهٔ ‌xor است). جفت‌های شوم یا بدشگون می‌توانند نحسی به همراه بیاورند اما اگر یک جفت همزمان هم شوم و هم بدشگون باشد، این دو نحسی یکدیگر را خنثی می‌کنند. بدین ترتیب یک جفت نحس است اگر و تنها اگر دقیقا یکی از دو شرط شومی یا بدشگونی را داشته باشد.

آقای دنباله‌نژاد نحسی دنباله را برابر تعداد جفت‌های نحس تعریف می‌کند و برای پیشگویی نیاز به دانستن نحسی دنباله دارد. اما آقای دنباله‌نژاد که دیگر پیر و فرتوت شده است نمی‌تواند به راحتی نحسی دنباله را محاسبه کند و به همین سبب از شما خواسته تا به او در پیشبینی کردن اتفاقات بد کمک کنید.

ورودی🔗

سطر اول ورودی، شامل دو عدد طبیعی $n$ طول دنباله و $k$ است. $1 \leq n \leq 10^6, \quad 0 \leq k < 2 ^ {30}$

در سطر بعدی، $n$ عدد می‌آید که عدد $i$م نشان دهندۀ $a_i$ است. $1 \leq a_i < 2^{30}$

خروجی🔗

در تنها سطر خروجی میزان نحسی دنباله را خروجی دهید.

زیرمسئله‌ها🔗

مثال‌ها🔗

ورودی نمونه ۱🔗

4 4
5 3 4 1

خروجی نمونه ۱🔗

4

ورودی نمونه ۲🔗

9 5
1 2 3 4 5 6 7 8 9

خروجی نمونه ۲🔗

20

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی دوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

در پی فرارهای مالیاتی، $n$ نفر به ترتیب به زندان می‌روند که زور نفر $i$م برابر $a_i$ است.

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

نگهبان زندان که زیاد شدن زور زندانی‌ها برایش نگران کننده شده است‌ (زیرا ممکن است شورش رخ دهد) از شما می‌خواهد که تعداد دفعات قوی‌تر شدن زندانی‌ها در تمام ترتیب‌های ممکن وارد شدن زندانی‌ها را به پیمانه $10^9 + 7$ برای او حساب کنید.

به عبارتی دیگر اگر تعداد قوی‌تر شدن‌ها برای ترتیب $\pi$ از زندانی‌ها برابر $f(\pi)$ و $T$ مجموعه همه‌ی $n!$ ترتیب ممکن باشد شما باید $\sum\limits_{\pi \in T} f(\pi)$ را حساب کنید.

ورودی🔗

در خط اول ورودی، تعداد زندانی‌ها یا همان $n$ می‌آید. $1 \leq n \leq 10^6$

در خط دوم، $n$ عدد می‌آید که عدد $i$م برابر $a_i$ یا همان زور نفر $i$م است. $1 \leq a_i \leq 10^9$

خروجی🔗

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

زیرمسئله‌ها🔗

مثال‌ها🔗

ورودی نمونه ۱🔗

3
2 1 2

خروجی نمونه ۱🔗

2

ورودی نمونه ۲🔗

6
4 5 5 5 3 3

خروجی نمونه ۲🔗

360