#P5537. Sequence

    ID: 4540 传统题 1500ms 512MiB 尝试: 7 已通过: 4 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模交换求和顺序组合数学补集计数多项式与生成函数普通生成函数生成函数求系数阶乘逆元预处理数论快速幂CF2400

Sequence

Sequence

题目描述

ysy是一位优秀的炉石传说玩家。

在2033年一次更新中,炉石新出了一张10费卡,它的效果如下:

检验对方场上的随从的生命值,求出最长连续相同的一段的长度,并对英雄造成等于这个长度的伤害。ysy觉得这张卡十分垃圾。

假设对面场上有 nn 个排成一列的随从,每个随从的生命值都是 [1,m][1,m] 内的整数,那么他想知道这张卡在所有情况下能打出的伤害之和。

他当然会算了,但是他想让你检验一下。由于答案可能会很大,对输入的质数p取模。

一句话题意:

共有 mnm^n 个长度为 nn 且每项取值为 11 到 mm 的序列。求每个序列的最长相同连续段长度之和。

最长连续相同子段长度就是最长的所有数都相同的一段的长度

例如{1,2,3,4,3,2,2,4,4,4,5}最长连续相同子段长度为3。

输入格式

一行三个整数 n,m,pn,m,p。

1≤n≤3000001\le n\le300000,2≤m≤1082\le m\le10^8,0.99×109≤p≤1.01×1090.99\times10^9\le p\le1.01\times10^9,且 pp 为质数。

输出格式

输出一行一个整数,即上述总和对 pp 取模的结果。

样例

10 2 998244353
3750