Migrated from Lutece 2671 柯蕾特与拉菲之章 - 祈祷天使大人

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

——「......你相信咱们会被拯救吗？」

——「我想......是的」

——「因为被拯救了而去相信，因为没有被拯救而不去相信」

「这种想法，是绝对得不到拯救的」

「咱们都很弱小，因为一点事就飘摇不定」

「所以，才要相信」

「并不是在被拯救之后才去相信......而是要去相信而得到救赎」

Active Planets - Musa $\space$

---

$\space$

圣女——在这个漂浮都市中十分重要的存在，需要每日早晚为这个城市的漂浮祈祷。由于先代圣女大人对祈祷工作的疏忽而导致「大崩落」的发生，教会为了平息人民的愤怒，将先代圣女进行了处刑示众。

向天使大人的祈祷结束后，第 29 代圣女伊莲回到了自己的房间准备休息。而在梦中，奇迹发生了：她梦见了天使大人对她的指示！

天使告诉她，天使大人的孩子——圣子降临在牢狱中。而为了知晓圣子的身份，天使给圣女出了一道题，如果她能在梦醒之前做出来，那么她便可以知晓圣子的身份并将其领回圣域，拯救这个城市。

题目与牢狱息息相关：由于此时的牢狱已经连成二叉树，而天使认为先代的二叉树并不美观，于是她想要重新规划牢狱，要求如下：

• 牢狱被划分为恰好 $n$ 个区域，每个区域的编号为 $1 \sim n$（每个编号恰好出现一次）。
• 区域之间仍然连成一棵二叉树，且其中一个叶子的编号恰好为 $X$。
• 满足大根堆的性质，即父亲节点编号大于儿子节点编号。

由于这个数比较大，圣女只需要说出答案对 $m$ 取模即可。为了都市的未来，圣女必须在梦醒之前解决该问题。

Input

输入一行仅包含三个正整数 $X,n,m$。

Output

输出一行表示答案。

Samples

2 4 114514

3

Constraints

$1\le X \le n \le 2021$ $1\le m \le 10^9$

Note

如图：

Resources

2021 UESTC ICPC Training for Math and Geometry