题目描述

两人轮流操作一个长度为 $n$ 的由字母表中前 $k$ 个字符组成的字符串。每次将字符串重新排列或删去一个字符，并不能和之前的字符串相同。不能操作者失败。

问有多少种字符串可以使得先手必胜，对质数 $p$ 取模。

输入格式

第一行三个整数 $n,k,p$，$1 \leqslant n \leqslant 250000$ ， $1 \leqslant k \leqslant 26$ ， $10^8 \leqslant p \leqslant 10^9+100$ ，且 $p$ 为质数。

输出格式

一个整数表示答案，对质数 $p$ 取模。

4 2 100000007

14