Problem 3C. 彩带染色

题目描述

请希望用 \(k\) 种颜色染色一条彩带，彩带可分为 \(n\) 小段。

请找出满足以下条件的染色方案数量。

• 彩带的每一小段恰被染成这 \(k\) 种颜色中的一种。
• 相邻的两段不能染同一颜色，即对于 \(1\le i< n\)，第 \(i\) 段彩带的颜色和第 \(i + 1\) 段彩带的颜色不同。

由于答案过大，请对 \(p\) 取模。

输入格式

三个正整数 \(k, n, p\)，表示颜色种数、彩带长度、模数。

输出格式

仅一个非负整数，表示染色数量。由于答案过大，请对 \(p\) 取模。

样例输入1

3 3 5

样例输出1

2

样例1解释

共有 12 种染色方案，如下：

[1, 2, 1] [1, 2, 3] [1, 3, 1] [1, 3, 2]

[2, 1, 2] [2, 1, 3] [2, 3, 1] [2, 3, 2]

[3, 1, 2] [3, 1, 3] [3, 2, 1] [3, 2, 3]

故输出 \(12\bmod 5=2\)

样例输入 2

19 2004 37

样例输出 2

11

样例输入 3

31415926535897932 38462643383279502 88419716939937510

样例输出 3

83030957998744842

数据范围及约定

本题共 \(120\) 分。

测试点编号	约定	测试点分值
1~3	\(1\le k,n,p\le 5\)	每个测试点 \(10\) 分
4~6	\(n=2\)	每个测试点 \(10\) 分
7~9	\(p = 998244353\)	每个测试点 \(10\) 分
10~12	无特殊约定	每个测试点 \(10\) 分

对于 \(100\%\) 的数据，\(1\le k,n,p\le 10^{18}\)。