Alice 和 Bob 正在玩一个包含字符串的游戏,Alice 先玩。该字符串由 n 个字符组成,每个字符都是字母表的前 k 个字母之一。轮到玩家时,他们可以任意排列单词中的字符,也可以删除单词中的一个字符(如果至少有一个字符)。此外,他们得出的单词不可能在整个游戏中出现过。无法做出有效动作的玩家输掉游戏。
给定 n、k、p,找到由字母表的前 k 个字母组成的恰好 n 个字符的单词数,这样如果 Alice 和 Bob 都表现最佳,则 Alice 将获胜。返回该数字以素数 p 为模。
输入
输入的第一行将包含三个整数 n、k、p(1 ≤ n ≤ 250 000、1 ≤ k ≤ 26、108 ≤ p ≤ 109 + 100,p 为素数)。
输出
打印一个整数,即 Alice 获胜单词的数量,以 p 为模。
示例
输入 #1
4 2 100000007
输出 #1
14
注意
Alice 可以用 14 个字符串获胜。例如,某些字符串是“bbaa”和“baaa”。 Alice 会输掉像“aaaa”或“bbbb”这样的字符串。