A5674. 「THUPC 2023」阴阳阵
编程题
NOI/NOI+/CTSC
知识点
题目描述
有一张图，图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同，黑点之间两两不同。
每个节点有一条出边，每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。
此时共有 $(n+m)^{n+m}$ 个方案，每个方案是一个有向基环树森林。
称一个方案是好的当且仅当其满足以下条件：
- 任何一个黑点都指向一个白点，
- 每个环上的黑点数量和白点数量的乘积是偶数。
你需要求出所有方案中好的方案数量，对输入模数 $P$ 取模。
每个节点有一条出边，每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。
此时共有 $(n+m)^{n+m}$ 个方案，每个方案是一个有向基环树森林。
称一个方案是好的当且仅当其满足以下条件：
- 任何一个黑点都指向一个白点，
- 每个环上的黑点数量和白点数量的乘积是偶数。
你需要求出所有方案中好的方案数量，对输入模数 $P$ 取模。
输入格式
输入一行三个整数 $n,m,P$，意义如题目描述所述。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
2 1 1000000
输出 #1
12
输入 #2
8 8 8888888
输出 #2
2973992
输入 #3
1000 1000 123456789
输出 #3
55105667
说明/提示
对于所有测试数据，$1 \le n,m \le 2000$，$1 \le P \le 10^9$。
你可能需要注意常数对算法效率产生的影响。
你可能需要注意常数对算法效率产生的影响。