صوفی (Sufi)

در کشور اسپادانا، مردم علاقه زیادی به تصوّف و صوفی‌ها دارند. به همین دلیل هر ساله در یک روز به خصوص صوفی‌ها یک نمایش در جهت هدایت همگانی اجرا می‌کنند.

در این کشور $n$ صوفی زندگی می‌کنند که با شماره‌های $1$ تا $n$ مشخص می‌شوند. هر صوفی یک مُراد دارد و مراد صوفی $i$ اُم، صوفی $i - 1$ اُم است و مراد صوفی شماره $1$ نیز خداست.

این $n$‌ صوفی در یک خط نمایش را اجرا می‌کنند. این خط $n+1$ جایگاه دارد که با شماره‌های $0$ تا $n$ از چپ به راست شماره‌گذاری شده‌اند. در ابتدا صوفی‌ها در جایگاه‌های $1, 2, …, n$ قرار دارند به طوری هیچ دو صوفی‌ای در یک جایگاه نیستند. در این نمایش نمادین، خدا همواره در جایگاه صفر خط قرار دارد.

این نمایش به این شکل انجام می‌شود که در هر مرحله دو بار تفنگ شلیک می‌شود.

• با شلیک اول تفنگ، هر صوفی به مرادش نگاه می‌کند جایگاه او را به خاطر می‌سپارد، سپس اگر جایگاه مرادش سمت چپش بود، تصمیم می‌گیرد که یک واحد به چپ برود، اگر جایگاه مرادش با جایگاه خودش یکسان بود، تصمیم می‌گیرد که حرکتی نکند و اگر مرادش سمت راست او بود، تصمیم می‌گیرد یک واحد به راست برود.
• با شلیک دوم تفنگ، هر صوفی حرکتی که در مرحله قبلی مدنظر داشت را انجام می‌دهد. (ممکن است در جایش باقی بماند)

نمایش وقتی پایان می‌یابد که همه صوفی‌ها در جایگاه صفر قرار بگیرند و به مراد واقعی‌شان برسند. دقت کنید در حین این مراحل، ممکن است در یک جایگاه بیش‌ از یک صوفی قرار بگیرند.

به عنوان مثال فرض کنید جایگاه ابتدایی صوفی‌ها به شکل زیر باشد، مراحل به این صورت خواهد بود. (خدا را با عدد صفر نمایش داده‌ایم)

$$ <\ 0 \ | \ 3 \ | \ 1 \ | \ 2 \ > \ \rightarrow \ <\ 0 \ | \ 1 \ | \ 2, 3 \ | \ > \ \rightarrow \ <\ 0, 1 \ | \ 2 \ | \ 3 \ | \ > \ \rightarrow \ <\ 0, 1, 2 \ | \ 3 \ | \ | \ > \ \rightarrow \ <\ 0, 1, 2, 3 \ | \ | \ | \ > $$

در مثال بالا جایگاه‌ها با $|$ جدا شده‌اند و هر صوفی معلوم شده است که در کدام جایگاه قرار دارد.

زیبایی یک نمایش از نظر مردم، تعداد مراحل آن است. مثلا زیبایی نمایش بالا، $4$ است. اکنون در آستانه اجرای نمایش، جایگاه تعدادی از صوفی‌ها معلوم شده است ولی بقیه صوفی‌ها هنوز جایگاه ابتدایی‌شان را مشخص نکرده‌اند. فرض کنید تعداد صوفی‌هایی که جایگاه اولیه‌شان مشخص نیست $k$ باشد. برنامه‌ای بنویسید که مجموع زیبایی همه نمایش‌های ممکن را محاسبه کند،‌ یعنی مجموع زیبایی نمایش‌ها به ازای همه حالاتی که می‌توان صوفی‌هایی که جایگاه‌ ابتدایی‌شان مشخص نیست را در جایگاه‌های خالی قرار داد ($k!$ حالت ممکن). از آن‌جایی که این عدد ممکن است بزرگ باشد، باقی‌مانده آن را در پیمانه $10^{9} + 7$ بیابید.

سطر اول ورودی شامل دو عدد $n, k$ که $n$ تعداد صوفی‌ها و $k$ تعداد صوفی‌هایی که جایگاه ابتدایی‌شان معلوم نیست را مشخص می‌کند.

در خط دوم $n$ عدد $a_1, a_2, …, a_n$ می‌آید که $a_i$ شماره صوفی است که در جایگاه $i$ قرار دارد. اگر $a_i = -1$ باشد یعنی این مکان، معین نشده است که جایگاه کدام صوفی است.

در تنها خط خروجی, جواب مساله را چاپ کنید.

• زیرمسئله اول (۸ نمره): $n \le 1000$ و $k = 0$.
• زیرمسئله دوم (۳۱ نمره): $k = 0$.
• زیرمسئله سوم (۲۳ نمره): $k=n$.
• زیرمسئله چهارم (۳۸ نمره): بدون محدودیت اضافی.

• $1 \le n \le 10^{5}$
• $0 \le k \le min(n, 100)$
• $a_i = -1$ یا $1 \leq a_i \leq n$
• برای هر $i$ و $j$ متمایز که $a_i,a_j \neq -1$ می‌دانیم $a_i \neq a_j$.
• تعداد $i$هایی که $a_i = -1$ برابر با $k$ است.