酒馆战棋也是蒜斜非常喜欢的游戏。他常常一边玩游戏一边思考着哲♂学问题。众所周知，当前的酒馆战棋的版本答案是多个圣盾剧毒的峰哥。作为一名善于发问的新世纪大学生，蒜斜想要明白当双方都拥有版本答案的时候，游戏会变成什么样呢？究竟是谁杀了峰哥，而峰哥又杀了谁呢？

现在，假设在酒馆战棋的一轮战斗中，战斗的一方有 $n$ 个随从，另一方有 $m$ 个随从，所有的随从都是圣盾剧毒的峰哥，问期望多少次进攻后战斗结束。

题目补充

在这儿，我们补充介绍一下峰哥的属性以及酒馆战棋的战斗流程。峰哥的卡牌如下图所示，在本题中，血量、攻击力、费用都没有意义，你只需要留意峰哥的特殊属性。

酒馆战棋的战斗流程为：

1. 战斗开始前，双方的随从按照从左到右的顺序被标上了序号。如果有 $k \in \{n,m\}$ 个随从，那么第一个随从的编号为 $1$，最后一个随从的编号为 $k$。其中编号为 $i+1$ 的随从在 $i$ 之后，编号为 $1$ 的随从在 $k$ 之后。
2. 双方轮流行动，随从多的一方先手，如果双方随从数相同，则等概率随机一方开始攻击。
3. 当前攻击的一方的一个随从进行攻击。如果当前回合是这一方的第一个攻击回合，则编号为 $1$ 的随从攻击，否则假设上一次这一方攻击的随从编号是 $x$，这一次由 $x$ 后面第一个还活着的随从攻击。注意，当只有一个随从存活的时候，可能出现 $x$ 再次攻击的情况。
4. 攻击的随从等概率随机挑选一个还存活的敌方随从攻击。攻击结果：无论是攻击的随从还是被攻击的随从，如果身上有圣盾，则圣盾失去；如果没有圣盾，则随从死亡。
5. 峰哥的效果触发：对于每一个当前没有圣盾的峰哥，如果有一个和它同一方的其他随从（不包括自己）在刚才的攻击中失去了圣盾，则它获得圣盾。
6. 如果存在一方没有任何随从存活，游戏结束。否则进入对方回合，回到步骤 $3$。

如果你对战斗流程依然不了解，你可以看这个视频。 该视频从 0:55 开始就对应本题 $n=m=6$ 的情况。

输入格式

输入三个整数 $n,m, p (1 \leq n,m \leq 2000, n+m < p \leq 10^9+7$ 且 $p$ 为质数 $)$

输出格式

输出一行一个整数，表示期望轮数对 $p$ 取模后的结果。即，如果期望轮数的最简分数表示为 $\frac{a}{b}$，你需要输出一个整数 $c$ 满足 $c \times b = a \text{ mod } p$。

1 1 3

2

1 2 5

2

限制与约定

Small Task: $n+m\leq 5$。

Large Task: $n,m \leq 2000$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载