Алиса и Боб играют в игру со строкой символов, они ходят по очереди, первой ходит Алиса. Строка состоит из n символов, каждый из них является одним из первых k символов алфавита. На своем ходу игрок может либо произвольным образом перемешать символы в строке, либо удалить из строки ровно один символ (если в строке есть хотя бы один символ). Кроме того, результирующая строка не может совпадать ни с одной строкой, встречавщейся ранее в игре. Игрок, который не может сделать корректный ход, проигрывает.
По данным n, k, p найдите число строк длины n, состоящих из первых k символов алфавита таких, что Алиса выиграет, если и Алиса, и Боб играют оптимально. Выведите это число по простому модулю p.
Выходные данные
Выведите одно целое число — число выигрышных для Алисы строк по модулю p.
Примечание
Выигрышными для Алисы являются 14 строк. Среди них строки «bbaa» и «baaa». Алиса проиграет на строках «aaaa» или «bbbb».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 100000007
|
14
|