• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۶۰۰ مگابایت

---

یک جایگشت از اعداد ۱ تا \(n\) را \(k\)- متناوب می‌گوییم، اگر هیچ زیردنباله‌ی متوالی در آن وجود نداشته باشد که طولش از \(k\) بیش‌تر باشد و یکنوا (صعودی یا نزولی) باشد. مثلا اگر \( n = 5 \)، جایگشت \( <1,5,2,3,4> \) ۲-متناوب نیست.

برنامه‌ای بنویسید که:

اعداد \(n\) و \(k\) و یک جایگشت \(n\) تایی \(k\)- متناوب را از ورودی بخواند.

با فرض این‌که همه جایگشت‌های \(n\) تایی \(k\)-متناوب را به ترتیب الفبایی مرتب کنیم، حساب کند که جایگشت داده شده چندمین جایگشت است.

ورودی

در سطر اول ورودی به ترتیب دو عدد \(n\) و \(k\) آمده است.

در سطر بعدی \(n\) عدد آمده است که عناصر یک جایگشت \(k\)- متناوب را مشخص می‌کنند.

\[ 2 \le k \le n \le 400 \]

خروجی

در تنها سطر خروجی، باقی‌مانده رتبه جایگشت داده شده را بر عدد \(10^9 + 7 \) بنویسید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۳۰	\( n \le 15 \)
۲	۲۰	\( n \le 100 \)
۳	۵۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5 2
1 3 2 5 4

خروجی نمونه ۱

1