P12040 [USTCPC 2025] 公平抉择

考虑到评测机性能差异，改为 400ms 时限。USTCPC 时限为 600ms。 **请注意本题非常规时空限制！** 所以要“费厄”，最好是首先看清对手，倘是些不配承受“费厄”的，大可以老实不客气；待到它也“费厄”了，然后再与它讲“费厄”不迟。(节选自鲁迅《论“费厄泼赖”应该缓行》) 克露丝卡尔酱选择困难！她甚至无法抉择午饭去吃什么，作为她的朋友，你需要和她一起完整**公平的抉择**。

克露丝卡尔酱在做选择，食堂共有 $n$ 种菜品可选，而她手里只有一个 $k$ 面的骰子(如果 $k = 2$ 则为硬币)。 为了落实公平抉择的理念，她希望她的策略选择到每个菜品的概率相等。 求她期望投掷次数的最小值，**答案对质数 $M$ 取模**。

一行三个正整数 $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$**。

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

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