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

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

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