Республиканская олимпиада по информатике. 2018 год

Задача C. Претенденты на ГОИ

Ограничение по времени:

1 секунда

Ограничение по памяти:

32 мегабайта

Каждые четыре года среди всех стран проводится <<Гладиаторская Олимпиада по Информатике>>. Это уникальное в своем роде соревнование, в котором участникам нужно иметь не только силу, но и высокий интеллект. В Берляндии сейчас приятная головная боль, в стране $N$ различных претендентов на Олимпиаду. Уровень каждого претендента обозначается числом, $i$-й претендент имеет уровень $i$. Берляндии как сильной в информатике стране разрешено отправлять любое количество участников на Олимпиаду, но в стране все равно планируют провести отбор. На отборочный раунд выбирается некоторое ненулевое количество претендентов, затем проводят $M$ туров. Далее в $i$-м туре проделываются следующие операции:

1. Если количество оставшихся претендентов хотя бы $a_i$, то список претендентов покидают $a_i$ претендентов с минимальным уровнем. Далее заново повторяется $i$-й тур.
2. Если количество оставшихся претендентов строго меньше чем $a_i$, то переходится к следующему туру. За исключением случая когда $i=M$, в этом случае отбор завершается.

Заметим тот факт, что после выбора претендентов на отборочные туры финальный список оставшихся претендентов определяется однозначно. Журналисты решили заранее описать всевозможные случаи и посчитать общее количество оставшихся претендентов по всем возможным изначальным выборкам претендентов. Так как это значение может быть большим выведите остаток по модулю $P$.

Формат входного файла

В первой строке входных данных даны три целых числа $M$, $N$ и $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — количество раундов, количество претендентов и число по которому надо взять остаток. Заметим, что $P$ необязательно простое число. В следующей строке даны $M$ целых чисел $a_i$ ($1 \le a_i \le 1000$) — число для $i$-го раунда.

Формат выходного файла

Выведите одно целое число — ответ на задачу.

Система оценки

Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 18$. Оценивается в $10$ баллов.
2. $n \le 1000$. Оценивается в $18$ баллов.
3. $n \le 10^6$, $P = 999999937$. Оценивается в $21$ баллов.
4. Только ограничения из условия. Оценивается в $51$ баллов.

Пример:

Вход

3 4 100000
7 3 4

Ответ

17

( Aidos Nurmash )