Description

克露丝卡尔酱在做选择，食堂共有 $n$ 种菜品可选，而她手里只有一个 $k$ 面的骰子(如果 $k = 2$ 则为硬币)。

为了落实公平抉择的理念，她希望她的策略选择到每个菜品的概率相等。

求她期望投掷次数的最小值，答案对质数 $M$ 取模。

Input Format

一行三个正整数 $n, k, M$ ,分别表示选项数、骰子面数和模数。

$2 \le k \le n \le 3 \times 10^6$，$10^8 \le M \le 10^9$，保证 $M$ 为质数且对于任意 $1 \le i \le n,k^i \bmod M > 1$。

Output Format

一个整数表示模意义下的答案。

关于分数取模：设答案为 $\dfrac{q}{p}$ 且 $M \nmid p,q$，那么取模结果 $x$ 为 唯一 $x\in[0,M)$ 使得 $px\equiv q\pmod M$。

3 2 998244353

665496238

10 2 998244353

798595487

Hint

在样例 $1$ 中，不妨设答案为 $E$。考虑扔两次硬币，得到四种情况，出现概率各为 $\dfrac{1}4$。前三种情况分配给三种菜品，第四种情况重投。故 $E=2+\dfrac{E}4$，解得 $E=\dfrac{8}3$。