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

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