E. Новогодняя гирлянда
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В то время как Геральд, Александр, Сергей и Геннадий уже занимаются привычными новогодними делами, Эдвард второпях наряжает новогоднюю елку. А какая елка без гирлянды? У Эдварда есть лампочки m цветов, и он хочет составить из них гирлянду — последовательность длины L. Елка Эдварда состоит из n ярусов, и Эдвард планирует расположить гирлянду таким образом, чтобы первые l1 лампочек гирлянды украшали первый ярус, следующие l2 лампочек — второй ярус и так далее, на последнем n-ом ярусе окажутся последние ln лампочек, Эдвард — любитель математических головоломок, поэтому его неожиданно заинтересовал вопрос: сколько у него различных вариантов собрать гирлянду, чтобы выполнялись оба условия:

  1. Любые две подряд идущие лампочки на каждом ярусе должны иметь разные цвета.
  2. Множества цветов лампочек на каждых двух соседних ярусах должны быть различны. Здесь рассматриваются неупорядоченные множества (не мультимножества), в которых каждый цвет встречается не более одного раза. То есть количество лампочек значения не имеет.

Помогите Эдварду получить ответ на мучающий его вопрос, иначе он не успеет нарядить елку до Нового года. Считайте, что у Эдварда бесконечное количество лампочек каждого из m цветов, причем использовать все m цветов необязательно. Гирлянды считаются различными, если они как последовательности различаются хотя бы в одной позиции. Вычислите ответ на задачу по заданному модулю p.

Входные данные

В первой строке заданы три целых числа n, m и p (1 ≤ n, m ≤ 106, 2 ≤ p ≤ 109) — количество ярусов елки, количество цветов лампочек и модуль, соответственно. Следующая строка содержит n целых чисел li (1 ≤ li ≤ 5000, ).

Выходные данные

Выведите одно число — количество гирлянд по модулю p.

Примеры
Входные данные
3 2 1000
3 1 2
Выходные данные
8
Входные данные
2 3 1000
2 2
Выходные данные
24
Входные данные
1 1 1000
5
Выходные данные
0
Примечание

В первом примере возможны следующие варианты: 121|1|12, 121|1|21, 121|2|12, 121|2|21, 212|1|12, 212|1|21, 212|2|12, 212|2|21. Во втором примере возможны варианты: 12|13, 12|23, 12|31, 12|32 и т.д.

Рисунок к первому примеру: