题目背景

“余于久远之书，见一阴阳阵，必可助君征服九州。用此阵，须出诸阴阳大将。所谓阴将者，武勇而玉恶；所谓阳将者，善谋时且忠厚。凡阴阳阵，各将皆须择一将，以通之。又有两法皆牢记，不可即弱阵：一曰阴援阴，易激性情，或避之；二曰援与环，环阴与阳同，守以衡……”

正当你准备征服九州时，你仿佛听见一个熟悉的声音在远处喊：“工作的时候不准睡觉，你这样会被开除的……”你终于回过神来，发现你的 XCPC 队友在旁边熟练地拧着螺丝，流水线前已经漏过几个不合格的工品。刚刚什么都没发生啊，你哀叹道，但是……

题目描述

有一张图，图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同，黑点之间两两不同。

每个节点有一条出边，每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。

此时共有 $(n+m)^{n+m}$ 个方案，每个方案是一个有向基环树森林。

称一个方案是好的当且仅当其满足以下条件：

• 任何一个黑点都指向一个白点，
• 每个环上的黑点数量和白点数量的乘积是偶数。

你需要求出所有方案中好的方案数量，对输入模数 $P$ 取模。

输入格式

输入一行三个整数 $n,m,P$，意义如题目描述所述。

输出格式

输出一行一个整数表示答案。

2 1 1000000

12

考虑黑点必须连向白点的限制共有 $3 \times 3 \times 2 = 18$ 种方案，其中一个黑点和一个白点构成一个环的方案非法。选择一个白点和黑点构成环的方案数为 $2$，剩下的一个白点有三种方案，因此非法的方案数为 $2 \times 3 = 6$，答案为 $18-6=12$。

8 8 8888888

2973992

1000 1000 123456789

55105667

数据范围与提示

对于所有测试数据，$1 \le n,m \le 2000$，$1 \le P \le 10^9$。

你可能需要注意常数对算法效率产生的影响。

题目使用协议

来自 THUPC2023（2023年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2023 官方仓库（https://github.com/THUSAAC/THUPC2023）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。