题目描述

热门游戏 Mokepon 可以表示为一列 $n$ 个站点，玩家从站点 $1$ 出发，站点中放有一些特殊道具。每件道具都有一个编号 $id$（$2\le id\le n$），任意两件道具的编号不同。玩家只有持有编号为 $i$ 的道具，才能从站点 $i-1$ 前往站点 $i$。每个站点可以放置任意件道具，也可以没有道具；玩家能够拾取并携带数量不限的道具。游戏目标是到达最后一个站点，即站点 $n$。

你和朋友觉得这款游戏太简单，于是决定把两局 Mokepon 联动起来：你的游戏有 $n_A$ 个站点，朋友的游戏有 $n_B$ 个站点。特殊道具可以出现在任意一局游戏中，现在每件道具由二元组 $(id,\mathrm A)$ 或 $(id,\mathrm B)$ 唯一标识，其中包含道具编号以及它属于哪一局游戏。要在某一局游戏中前进到站点 $i$，你们二人中的任意一人必须已经拾取属于该局、编号为 $i$ 的道具。

游戏会随机决定每件道具放在哪一局的哪个站点，因此并非每一种放置方案都能获胜。请计算有多少种道具分布能让你们二人都到达各自游戏的最后一个站点。答案可能很大，请对质数 $p$ 取模。

如果至少存在一个站点，其所含道具集合在两种方案中不同，就认为这两种道具分布不同。

输入格式

输入仅一行，包含三个整数 $n_A,n_B,p$（$2\le n_A,n_B\le3\cdot10^3$，$10^8\le p\le10^9+7$），分别表示你与朋友的游戏所含站点数，以及计算答案时使用的模数。

保证 $p$ 是质数。

输出格式

输出一个整数，表示能让两名玩家分别赢得自己游戏的道具分布数，对 $p$ 取模。

2 2 1000000007

8

15 20 998244353

937612

提示

在样例 1 中，特殊道具共有两件：属于游戏 A 的 $(2,\mathrm A)$ 和属于游戏 B 的 $(2,\mathrm B)$。每件道具都可以放在四个“站点—游戏”位置中的任意一个，因此一共有 $4^2=16$ 种放置方案。

以下列出八种能够获胜的方案。每一项中的第一个位置是道具 $(2,\mathrm A)$ 所在处，第二个位置是道具 $(2,\mathrm B)$ 所在处；位置记为“（站点，游戏）”。

1. $(1,\mathrm A);(1,\mathrm A)$：两名玩家都能立即前往各自的终点站；
2. $(1,\mathrm A);(2,\mathrm A)$：第一名玩家先解锁自己的终点站，随后第二名玩家便可前进；
3. $(1,\mathrm A);(1,\mathrm B)$；
4. $(1,\mathrm B);(1,\mathrm A)$；
5. $(1,\mathrm B);(1,\mathrm B)$；
6. $(1,\mathrm B);(2,\mathrm A)$；
7. $(2,\mathrm B);(1,\mathrm A)$；
8. $(2,\mathrm B);(1,\mathrm B)$。