该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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$ 分。

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