鲍勃发现了一个新的有趣的游戏。在这个游戏中，鲍勃有 $n$ 个敌人要打，而每个敌人都有 $m$ 种颜色之一的颜色。在一个回合中，鲍勃可以攻击一段连续的敌人，这些敌人必须有相同的颜色。
鲍勃想尽可能多地攻击敌人，但有时他并不满足。对于每一种颜色的设定，我们称鲍勃的幸福感为他在一个回合中可以攻击的最大数量的敌人。鲍勃想知道对于所有 $m^n$ 种可能的敌人颜色设置，他的幸福感之和。由于这个数字可能很大，你需要输出它对一个给定素数取模的结果。
Implementation Details
你应该包含 coloring.h，并实现如下过程：
int totalhappy(int n, int m, int p)
- $n$: 敌人的数量。
- $m$: 总颜色数。
- $p$: 模数。一个质数。
- 你实现的过程会被调用恰好一次。
- 你应该返回所有上色方案的幸福感之和对 $p$ 取余的值：一个 $[0,p-1]$ 的整数。
Example
考虑如下调用：totalhappy(2, 2, 998244353)
如果两个敌人颜色相同，鲍勃的幸福感为 $2$，否则为 $1$。因此，总幸福感为 $2+2+1+1=6$。一个正确的程序应该返回 $6\bmod 998244353=6$。
Constraints
$1\le n\le 10^6$
$1\le m\le 10^9$
$10^8 < p< 10^9$，$p$ 为质数。
Subtasks
- （10分）$n\le 10$，$m\le 4$
- （20分）$n\le 100$
- （30分）$n\le 50000$
- （20分）$m\le 10^6$
- （20分）无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 一行：$n~m~p$
样例交互器以下列格式打印你的输出。
- 一行，你的返回值