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

---

علی‌جان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او می‌داند رمز گاوصندوقش جایگشتی از اعداد $1$ تا $n$ می‌باشد. علی‌جان از گاوصندوق هوشمند راهنمایی می‌گیرد تا رمز را پیدا کند. اگر رمز گاوصندوق جایگشت $s = \langle s_1, s_2, \cdots, s_n \rangle\ $ باشد، ابتدا عملیات زیر را انجام می‌دهد، و سپس جایگشت نهایی را به علی‌جان می‌دهد.

علی‌جان مقدار $k$ و جایگشت بعد از اجرا شدن کد بالا روی آن را دارد. او می‌خواهد بداند چند دنباله مختلف ممکن است رمز گاوصندوقش باشد.

ورودی

در خط اول ورودی دو عدد طبیعی $n$ و سپس $k$ به‌ترتیب می‌آیند.

در خط دوم ورودی $n$ عدد $s_1, s_2, \cdots, s_n\ $ به‌ترتیب می‌آیند.

خروجی

در تنها خط خروجی، تعداد دنباله‌های مختلفی که می‌توانند رمز گاوصندوق باشند را چاپ کنید. از آنجایی که این مقدار ممکن است بزرگ باشد، باقی‌مانده تقسیم آن بر $10^9+7$ را چاپ کنید.

محدودیت‌ها

$$2 \leq n, k \leq 200 , 000$$ $$1 \leq s_i \leq n$$

• شرط $s_i \neq s_j$ به ازای تمامی $i \neq j$ برقرار می‌باشد.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۰	$n \leq 15$
۲	۲۱	$k = 1$
۳	۲۹	$k = 2$ و $n \leq 2000$
۴	۱۷	$ k \leq 50$
۵	۲۳	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 1
1 2 3 4

خروجی نمونه ۱

8

ورودی نمونه ۲

6 2
5 1 3 4 2 6

خروجی نمونه ۲

2

جایگشت $\langle 3, 5, 1, 6, 4, 2 \rangle\ $ یکی از جایگشت‌هایی است که ممکن است رمز گاوصندوق دوم باشد. عملیات‌هایی که روی این جایگشت انجام می‌شود:

1. در مرحله اول، $s_1 > \min(s_2, s_3)\ $ می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 3, 1, 6, 4, 2 \rangle$ تبدیل می‌شود.
2. در مرحله دوم، $s_2 > \min(s_3, s_4)$ می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 1, 3, 6, 4, 2 \rangle$ تبدیل می‌شود.
3. در این مرحله جابه‌جایی انجام نمی‌دهد.
4. در این مرحله مجددا جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 1, 3, 4, 6, 2 \rangle$ تبدیل می‌شود.
5. در مرحله آخر نیز جابه‌جایی انجام می‌شود و به جایگشت نهایی $\langle 5, 1, 3, 4, 2, 6 \rangle$ تبدیل می‌شود.