+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- علی‌جان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او می‌داند رمز گاوصندوقش جایگشتی از اعداد $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$ تبدیل می‌شود.