F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5537. -- Sequence

5537: Sequence

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Discuss]

Description

ysy是一位优秀的炉石传说玩家。
在2033年一次更新中,炉石新出了一张10费卡,它的效果如下:
检验对方场上的随从的生命值,求出最长连续相同的一段的长度,
并对英雄造成等于这个长度的伤害。ysy觉得这张卡十分垃圾。
假设对面场上有n个随从,生命值为[1,m]的整数,那么他想知道这张
卡在所有情况下能打出的伤害之和。
他当然会算了,但是他想让你检验一下。由于答案可能会很大,对输入的质数p取模。
一句话题意:
你需要求出所有长度为n的
每个元素为[1,m]的整数的mn个序列的最长连续相同子段长度之和。
最长连续相同子段长度就是最长的所有数都相同的一段的长度
例如{1,2,3,4,3,2,2,4,4,4,5}最长连续相同子段长度为3。

Input

一行三个整数n、m、p。
1 ≤ n ≤ 300000, 2 ≤ m ≤ 10^8, 
0.99 × 10^9 ≤ p ≤ 1.01 × 10^9 且 p 为质数

Output

一行答案

Sample Input

10 2 998244353

Sample Output

3750

HINT

Source

[Submit][Status][Discuss]

HOME Back