+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه $a$ شامل اعداد $a_1, a_2, ..., a_n$ را در نظر بگیرید، به دنباله ناتهی $x_1, x_2, ..., x_k$ از اعداد $1$ تا $n$ تورج‌پسند گفته می‌شود، اگر - برای هر $1 \le i < k$ و هر $x_i < j < x_{i+1}$ داشته باشیم $a_{x_i} \le a_j \le a_{x_{i+1}} \; \;$ - $1 \le x_1 < x_2 < ... < x_k \le n$ - $a_{x_1} \le a_{x_2} \le ... \le a_{x_n}$ آقا تورج برای استخدام کارمند در شرکتش، آرایه $a$ را به مراجعین می‌دهد و در صورتی که بتوانند باقی‌مانده تعداد دنباله‌های تورج‌پسند آن را بر $10 ^ 9 + 7$ بیابند آن‌ها را استخدام می‌کند.\ پوپک که از دانش‌پژوهان سابق المپیاد کامپیوتر است، به تازگی شیفته کار در شرکت آقا تورج شده است. او از شما می‌خواهد در راه استخدام در شرکت به او کمک کنید. # ورودی خط اول ورودی شامل عدد $n$ است که طول آرایه $a$ را مشخص می‌کند. + $1 \le n \le 5 \times 10^{5}$ + $1 \le a_i \le 10^9$ # خروجی در تنها خط خروجی، باقی‌مانده تعداد دنباله‌های تورج پسند آرایه $a$ را بر $10 ^ 9 + 7$ چاپ کنید. # زیر مسئله ها | زیرمسئله | نمره | محدودیت ها | |:-----------:|:------------------:|:------------------:| | ۱ | ۷ | $n \le 20$ | | ۲ | ۱۵ | $n \le 5000$ | | ۳ | ۷۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 7 ``` ## ورودی نمونه ۲ ``` 4 5 2 1 6 ``` ## خروجی نمونه ۲ ``` 5 ```

دنباله

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

آرایه $a$ شامل اعداد $a_1, a_2, ..., a_n$ را در نظر بگیرید، به دنباله ناتهی $x_1, x_2, ..., x_k$ از اعداد $1$ تا $n$ تورج‌پسند گفته می‌شود، اگر

برای هر $1 \le i < k$ و هر $x_i < j < x_{i+1}$ داشته باشیم $a_{x_i} \le a_j \le a_{x_{i+1}} \; \;$
$1 \le x_1 < x_2 < ... < x_k \le n$
$a_{x_1} \le a_{x_2} \le ... \le a_{x_n}$

آقا تورج برای استخدام کارمند در شرکتش، آرایه $a$ را به مراجعین می‌دهد و در صورتی که بتوانند باقی‌مانده تعداد دنباله‌های تورج‌پسند آن را بر $10 ^ 9 + 7$ بیابند آن‌ها را استخدام می‌کند.
پوپک که از دانش‌پژوهان سابق المپیاد کامپیوتر است، به تازگی شیفته کار در شرکت آقا تورج شده است. او از شما می‌خواهد در راه استخدام در شرکت به او کمک کنید.

ورودی🔗

خط اول ورودی شامل عدد $n$ است که طول آرایه $a$ را مشخص می‌کند.

$1 \le n \le 5 \times 10^{5}$
$1 \le a_i \le 10^9$

خروجی🔗

در تنها خط خروجی، باقی‌مانده تعداد دنباله‌های تورج پسند آرایه $a$ را بر $10 ^ 9 + 7$ چاپ کنید.

زیر مسئله ها🔗

زیرمسئله	نمره	محدودیت ها
۱	۷	$n \le 20$
۲	۱۵	$n \le 5000$
۳	۷۸	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

3
1 2 3

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

4
5 2 1 6

خروجی نمونه ۲🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کشور اسپادانا، مورد حمله تعدادی گروه تروریستی قرار گرفته است که هر گروه تروریستی شامل تعدادی هوایپمای جنگنده است.\ می‌دانیم جنگنده‌ها وارد جو زمین شده‌اند و قصد حمله به اسپادانا را دارند. خشایارشاه، پادشاه اسپادانا، هم‌اکنون متوجه حضور دشمنان در مرز هوایی کشورش شده است. لذا به مگنولیا، مشاور اعظم، دستور روشن کردنِ دستگاه «مگنول‌خفن» را داده است. با روشن کردن این دستگاه، موتور تمام جنگنده‌ها از کار می‌افتد و تنها تحت تاثیر جاذبه و فقط به سمت پایین سقوط می‌کنند لذا با این تدبیر هوشمندانه، توطئه دشمن به کلی ساقط می شود. آسمان اسپادانا به صورت یک جدول $n \times m$ است که در هر خانه از این جدول یا یک جنگنده قرار دارد یا خالی است. در پایین جدول هم سطح زمین اسپادانا قرار دارد. در مورد حرکت گروه‌های تروریستی مگنولیا اطلاعات زیر را جمع‌آوری کرده است. - همه ‌جنگنده‌های یک گروه تروریستی به صورت یکسان حرکت می‌کنند، یعنی وضعیت نسبی جنگنده‌های یک گروه تروریستی تغییر نمی‌کند. - هیچ دو جنگنده‌ای نمی‌توانند از روی هم عبور کنند و یا در یک جا قرار بگیرند. - جنگنده‌ها تحت تاثیر جاذبه تا حد امکان به سمت پایین سقوط می‌کنند. مگنولیا جهت چاپلوسی بیشتر خدمت خشایارشاه، می‌خواهد وضعیت نهایی جنگنده‌ها را به خشایار‌شاه گزارش دهد. شما این وضعیت نهایی را برای مگنولیا چاپ کنید. پس از مطالعه شیوه گرفتن ورودی و نمایش خروجی، جهت فهم بهتر سوال، تست‌های نمونه را نیز مشاهده کنید. # ورودی خط اول وروی شامل دو عدد $n, m$ است که ابعاد آسمان دوبعدی اسپادانا را معلوم می‌کند.\ سپس در $n$ سطر هر سطر $m$ عدد می‌آید که اطلاعات آسمان است. در ستون $1 \le j \le m$ از سطر $i+1$ اُم ورودی عدد $a_{i, j}$ می‌آید که شماره گروه جنگنده موجود در آن مکان است. اگر $a_{i, j} = 0$ یعنی آن مکان خالی است. و جنگنده‌ای در آن نقطه وجود ندارد. + $1 \le n, m \le 1000$ + $0 \le a_{i, j} \le n \times m$ # خروجی خروجی باید وضعیت نهایی آسمان اسپادانا باشد.\ یعنی در $n$ سطر و در هر سطر $m$ عدد نمایش دهید که وضعیت نهایی آن خانه را نشان می‌دهد.\ یعنی باید یا شماره گروه یک جنگنده را نمایش دهید یا اگر آن خانه خالی است $0$ چاپ کنید. # زیر مسئله ها | زیرمسئله | نمره | محدودیت ها | |:-----------:|:------------------:|:------------------:| | ۱ | ۵ | $n = 2$ | | ۲ | ۵ | $a_{i, j} \le 2$ | | ۳ | ۱۵ | $n \times m \le 1000$ | | ۴ | ۲۰ | $a_{i, j} \le 200$ | | ۵ | ۲۵ | برای هر گروه تروریستی‫‪،‬جنگنده های این گروه تشکیل یک مستطیل در آسمان اسپادانا می دهند. | | ۶ | ۳۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 2 1 2 0 2 ``` ## خروجی نمونه ۱ ``` 0 2 1 2 ``` ## ورودی نمونه ۲ ``` 4 3 1 1 1 1 2 1 1 1 1 0 0 0 ``` ## خروجی نمونه ۲ ``` 0 0 0 1 1 1 1 2 1 1 1 1 ``` ## ورودی نمونه ۳ ``` 5 5 1 1 1 0 0 0 0 2 2 1 3 0 0 0 4 3 0 4 0 0 0 0 0 0 0 ``` ## خروجی نمونه ۳ ``` 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 3 0 2 2 4 3 0 4 0 0 ``` ## ورودی نمونه ۴ ``` 3 2 1 2 2 1 0 0 ``` ## خروجی نمونه ۴ ``` 0 0 1 2 2 1 ```

تجاوز هوایی

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

کشور اسپادانا، مورد حمله تعدادی گروه تروریستی قرار گرفته است که هر گروه تروریستی شامل تعدادی هوایپمای جنگنده است.
می‌دانیم جنگنده‌ها وارد جو زمین شده‌اند و قصد حمله به اسپادانا را دارند. خشایارشاه، پادشاه اسپادانا، هم‌اکنون متوجه حضور دشمنان در مرز هوایی کشورش شده است. لذا به مگنولیا، مشاور اعظم، دستور روشن کردنِ دستگاه «مگنول‌خفن» را داده است.

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

آسمان اسپادانا به صورت یک جدول $n \times m$ است که در هر خانه از این جدول یا یک جنگنده قرار دارد یا خالی است. در پایین جدول هم سطح زمین اسپادانا قرار دارد.

در مورد حرکت گروه‌های تروریستی مگنولیا اطلاعات زیر را جمع‌آوری کرده است.

همه ‌جنگنده‌های یک گروه تروریستی به صورت یکسان حرکت می‌کنند، یعنی وضعیت نسبی جنگنده‌های یک گروه تروریستی تغییر نمی‌کند.
هیچ دو جنگنده‌ای نمی‌توانند از روی هم عبور کنند و یا در یک جا قرار بگیرند.
جنگنده‌ها تحت تاثیر جاذبه تا حد امکان به سمت پایین سقوط می‌کنند.

مگنولیا جهت چاپلوسی بیشتر خدمت خشایارشاه، می‌خواهد وضعیت نهایی جنگنده‌ها را به خشایار‌شاه گزارش دهد. شما این وضعیت نهایی را برای مگنولیا چاپ کنید.

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

ورودی🔗

خط اول وروی شامل دو عدد $n, m$ است که ابعاد آسمان دوبعدی اسپادانا را معلوم می‌کند.
سپس در $n$ سطر هر سطر $m$ عدد می‌آید که اطلاعات آسمان است. در ستون $1 \le j \le m$ از سطر $i+1$ اُم ورودی عدد $a_{i, j}$ می‌آید که شماره گروه جنگنده موجود در آن مکان است. اگر $a_{i, j} = 0$ یعنی آن مکان خالی است. و جنگنده‌ای در آن نقطه وجود ندارد.

$1 \le n, m \le 1000$
$0 \le a_{i, j} \le n \times m$

خروجی🔗

خروجی باید وضعیت نهایی آسمان اسپادانا باشد.
یعنی در $n$ سطر و در هر سطر $m$ عدد نمایش دهید که وضعیت نهایی آن خانه را نشان می‌دهد.
یعنی باید یا شماره گروه یک جنگنده را نمایش دهید یا اگر آن خانه خالی است $0$ چاپ کنید.

زیر مسئله ها🔗

زیرمسئله	نمره	محدودیت ها
۱	۵	$n = 2$
۲	۵	$a_{i, j} \le 2$
۳	۱۵	$n \times m \le 1000$
۴	۲۰	$a_{i, j} \le 200$
۵	۲۵	برای هر گروه تروریستی‫‪،‬جنگنده های این گروه تشکیل یک مستطیل در آسمان اسپادانا می دهند.
۶	۳۰	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

2 2
1 2
0 2

خروجی نمونه ۱🔗

0 2
1 2

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

ورودی نمونه ۴🔗

خروجی نمونه ۴🔗

0 0
1 2
2 1

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور اسپادانا، مردم علاقه زیادی به تصوّف و صوفی‌ها دارند. به همین دلیل هر ساله در یک روز به خصوص صوفی‌ها یک نمایش در جهت هدایت همگانی اجرا می‌کنند.\ در این کشور $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$ باشد یعنی این مکان، معین نشده است که جایگاه کدام صوفی است. + برای هر $i$ و $j$ متمایز که $a_i,a_j \neq -1$ می‌دانیم $a_i \neq a_j$ + تعداد $i$ هایی که $a_i = -1$ برابر با $k$ است. + $1 \le n \le 10^{5}$ + $0 \le k \le min(n, 100)$ + $a_i = -1$ یا $1 \le a_i \le n$ # خروجی در تنها خط خروجی, جواب مساله را چاپ کنید. # زیر مسئله ها | زیرمسئله | نمره | محدودیت ها | |:-----------:|:------------------:|:------------------:| | ۱ | ۸ | $n \le 1000$ , $k = 0$ | | ۲ | ۳۱ | $k = 0$ | | ۳ | ۲۳ | $k = n$ | | ۴ | ۳۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 0 3 1 2 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 2 3 -1 -1 ``` ## خروجی نمونه ۲ ``` 9 ```

صوفی

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

در کشور اسپادانا، مردم علاقه زیادی به تصوّف و صوفی‌ها دارند. به همین دلیل هر ساله در یک روز به خصوص صوفی‌ها یک نمایش در جهت هدایت همگانی اجرا می‌کنند.
در این کشور $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$ باشد یعنی این مکان، معین نشده است که جایگاه کدام صوفی است.

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

خروجی🔗

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

زیر مسئله ها🔗

زیرمسئله	نمره	محدودیت ها
۱	۸	$n \le 1000$ , $k = 0$
۲	۳۱	$k = 0$
۳	۲۳	$k = n$
۴	۳۸	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

3 0
3 1 2

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

3 2
3 -1 -1