+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- راک پس از ساخت تانک‌ها قرار است به قلعه‌ی کاکا حمله کند. قلعه توسط دیواری دفاعی محافظت میشود. کاکا می‌داند تانک $i$ ام بازه $[l_i, r_i]$ دیوار دفاعی سرزمینش را هدف گرفته. با شلیک زیرمجموعه‌ای از تانک‌های راک، تمامی قسمت‌های دیوار که حداقل یک تانک به آن شلیک کند تخریب میشود. برای بازسازی دیوار کاکا باید به تعداد مولفه‌های قسمت‌های تخریب شده به توان $k$ هزینه کند (یعنی اگر تعداد مولفه‌های خراب شده $x$ باشد، باید $x ^ k$ هزینه کند). برای فهم بیشتر به توضیحات ورودی نمونه مراجعه کنید. مجموع هزینه بازسازی دیوار به‌ازای تمامی زیرمجموعه‌های ناتهی از تانک‌هایی که شلیک می‌کنند را محاسبه کنید و مقدار حساب شده را باقیمانده بر $10 ^ 9 + 7$ به کاکا بگویید. # ورودی در خط اول ورودی $n$ و $k$ به شما داده میشود. در هر یک از $n$ خط بعد دو عدد $l_i$ و $r_i$ داده میشود. $(l_i < r_i)$ **نکته: تمامی $l_i, r_i$ ها $2n$ عدد متمایز عضو $\{1, 2, \dots, 2n\}$ هستند.** $n \le 10 ^ {5}, 2 \le k \le 10$ # خروجی پاسخ مسئله را باقیمانده بر $10 ^ 9 + 7$ چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۶ | $ n \le 16 $ | | ۲ | ۲۰ | $ n \le 1000 , k = 2 $ | | ۳ | ۲۰ | $ n \le 1000 $ | | ۴ | ۵۴ | بدون محدودیت بیشتر| ## ورودی نمونه ۱ ``` 3 2 1 6 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 10 ``` هزینه بازسازی برای هر زیرمجموعه از تانک‌هایی که شلیک می‌کنند در پایین نوشته شده: $$\{[1, 6]\} : 1$$ $$\{[2, 3]\} : 1$$ $$\{[4, 5]\} : 1$$$$\{[4, 5], [1, 6]\} : 1$$ $$\{[1, 6], [2, 3]\} : 1$$ $$\{[4, 5], [2, 3]\} : 4$$ $$\{[2, 3], [1, 6], [4, 5]\} : 1$$