C. Будущий проигрыш
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру со строкой символов, они ходят по очереди, первой ходит Алиса. Строка состоит из n символов, каждый из них является одним из первых k символов алфавита. На своем ходу игрок может либо произвольным образом перемешать символы в строке, либо удалить из строки ровно один символ (если в строке есть хотя бы один символ). Кроме того, результирующая строка не может совпадать ни с одной строкой, встречавщейся ранее в игре. Игрок, который не может сделать корректный ход, проигрывает.

По данным n, k, p найдите число строк длины n, состоящих из первых k символов алфавита таких, что Алиса выиграет, если и Алиса, и Боб играют оптимально. Выведите это число по простому модулю p.

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

Первая строка содержит три целых числа n, k, p (1 ≤ n ≤ 250 000, 1 ≤ k ≤ 26, 108 ≤ p ≤ 109 + 100, p простое).

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

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

Пример
Входные данные
4 2 100000007
Выходные данные
14
Примечание

Выигрышными для Алисы являются 14 строк. Среди них строки «bbaa» и «baaa». Алиса проиграет на строках «aaaa» или «bbbb».