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

说明

本题不再额外提供样例文件。

题目描述

N 个格子排成一排，第 i （1 ≤ i < N）个和第 i+1 个格子相邻。现在让你往格子里填数，所填数为不超过 M 的正整数。每个格子只能填一个数，不能不填。要求至少有两个相邻的格子填的数相同。

问：将全部格子填完有多少种不同的填法？答案可能很大，你需要将其 mod P 后输出。

两种填法不同，当前仅当至少存在同一个格子在两种填法中所填的数字不同。

输入格式

一行，三个整数 M, N, P

输出格式

一个整数，表示答案

样例1输入

2 3 123

样例1输出

6

样例2输入

123456789 9876543210 1000000007

样例2输出

10701959

数据范围

30%的数据满足：$1 ≤ M, N ≤ 10^4$

100%的数据满足：$1 ≤ M <= 10^9, 1 ≤ N ≤ 10^{15}, 1< P < 2^{31}$