D. Финал INOI
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня финал INOI (Иранская национальная олимпиада по информатике). Зал для контеста представляет собой ряд из $$$n$$$ компьютеров. Все компьютеры пронумерованы целыми числами от $$$1$$$ до $$$n$$$ слева направо. Всего будет $$$m$$$ участников, пронумерованных целыми числами от $$$1$$$ до $$$m$$$.

У нас есть массив $$$a$$$ длины $$$m$$$, где $$$a_{i}$$$ ($$$1 \leq a_i \leq n$$$) — это компьютер, около которого $$$i$$$-й участник хочет сесть.

Также у нас есть другой массив $$$b$$$ длины $$$m$$$, состоящий из символов «L» и «R». $$$b_i$$$ — это сторона, с которой $$$i$$$-й участник заходит в зал. «L» обозначает, что участник заходит в зал левее $$$1$$$-го компьютера, и идет слева направо, а «R» обозначает, что участник заходит в зал правее $$$n$$$-го компьютера, и идет справа налево.

Участники в порядке от $$$1$$$ до $$$m$$$ заходят в зал один за другим. $$$i$$$-й из них заходит в зал со стороны $$$b_i$$$ и идет до компьютера $$$a_i$$$. Если этот компьютер уже занят, он продолжает идти в том же направлении до первого не занятого компьютера. После этого он садится за этот компьютер. Если участник не встречает ни одного свободного компьютера, он расстраивается и покидает соревнование.

Расстроенность $$$i$$$-о участника — это расстояние между его желаемым компьютером ($$$a_i$$$) и компьютером, за который он в итоге сел. Расстояние между компьютерами $$$i$$$ и $$$j$$$ равно $$$|i - j|$$$.

Числа в массиве $$$a$$$ могут быть равны. Существует $$$n^m \cdot 2^m$$$ возможных пар массивов $$$(a, b)$$$.

Рассмотрим все пары массивов $$$(a, b)$$$ такие, что ни один участник не расстроится. Для каждой из них посчитаем сумму расстроенностей всех участников. Найдите сумму этих чисел.

Вам будет дан некоторый простой модуль $$$p$$$. Найдите эту сумму по модулю $$$p$$$.

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

В единственной строке находится три целых числа $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \leq m \leq n \leq 500, 10^8 \leq p \leq 10 ^ 9 + 9$$$).

Гарантируется, что число $$$p$$$ простое.

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

Выведите единственное целое число — необходимую сумму по модулю $$$p$$$.

Примеры
Входные данные
3 1 1000000007
Выходные данные
0
Входные данные
2 2 1000000009
Выходные данные
4
Входные данные
3 2 998244353
Выходные данные
8
Входные данные
20 10 1000000009
Выходные данные
352081045
Примечание

В первом тесте есть три возможных массива $$$a$$$: $$$\{1\}$$$, $$$\{2\}$$$ и $$$ \{3\}$$$ и два возможных массива $$$b$$$: $$$\{\mathtt{L}\}$$$ и $$$\{\mathtt{R}\}$$$. Для всех шести возможных пар массивов $$$(a, b)$$$ единственный участник сядет за компьютером $$$a_1$$$ (потому что он точно окажется не занят), поэтому его расстроенность будет равна $$$0$$$. Поэтому сумма всех расстоенностей будет равна $$$0$$$.

Во втором тесте все возможные пары массивов $$$(a, b)$$$ такие, что ни один участник не будет расстроен:

  • $$$(\{1, 1\}, \{\mathtt{L}, \mathtt{L}\})$$$, сумма расстроенностей $$$1$$$;
  • $$$(\{1, 1\}, \{\mathtt{R}, \mathtt{L}\})$$$, сумма расстроенностей $$$1$$$;
  • $$$(\{2, 2\}, \{\mathtt{R}, \mathtt{R}\})$$$, сумма расстроенностей $$$1$$$;
  • $$$(\{2, 2\}, \{\mathtt{L}, \mathtt{R}\})$$$, сумма расстроенностей $$$1$$$;
  • все возможные пары массивов $$$a \in \{\{1, 2\}, \{2, 1\}\}$$$ и $$$b \in \{\{\mathtt{L}, \mathtt{L}\}, \{\mathtt{R}, \mathtt{L}\}, \{\mathtt{L}, \mathtt{R}\}, \{\mathtt{R}, \mathtt{R}\}\}$$$, сумма расстроенностей $$$0$$$.

Поэтому ответ равен $$$1 + 1 + 1 + 1 + 0 \ldots = 4$$$.