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

یک جایگشت از اعداد ۱ تا $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$ بنویسید.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

5 2
1 3 2 5 4

خروجی نمونه ۱

1