Description

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

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

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

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

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

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

Input Format

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

Output Format

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

2 1 1000000

12

8 8 8888888

2973992

1000 1000 123456789

55105667

Hint

样例 1 解释

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

数据规模与约定

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

提示

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

题目来源

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

题解等资源可在 https://github.com/THUSAAC/THUPC2023 查看。