گاوصندوق (Safebox)

علی‌جان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او می‌داند رمز گاوصندوقش جایگشتی از اعداد $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$ و $n \leq 2000$
• زیرمسئله ۳ (۲۹ نمره): $k = 2$ و $n \leq 2000$
• زیرمسئله ۴ (۱۷ نمره): $k \leq 50$
• زیرمسئله ۵ (۲۳ نمره): بدون محدودیت اضافی

$\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$ تبدیل می‌شود.