Background

"In ancient texts, I came across a Yin-Yang Formation that could aid you in conquering the nine provinces. To use this formation, one must deploy both Yin and Yang generals. The Yin general is brave yet malevolent; the Yang general is wise and loyal. In any Yin-Yang Formation, each general must choose a counterpart to connect with. There are two rules to remember, to avoid a weak formation: firstly, Yin supporting Yin can stir emotions, perhaps to be avoided; secondly, support and loop, where the loop can be Yin or Yang, must be balanced..."

As you prepare to conquer the nine provinces, you seem to hear a familiar voice calling from afar: "No sleeping on the job, or you'll get fired..." You snap back to reality, finding your XCPC teammates skillfully tightening screws beside you, with a few defective products already slipping past the assembly line. Nothing happened just now, you lament, but...

Problem Description

There is a graph with $n$ white points and $m$ black points. The white points are pairwise distinct, and so are the black points.

Each node has one outgoing edge, and the destination of each outgoing edge can be chosen arbitrarily among the $n+m$ nodes.

There are $(n+m)^{n+m}$ possible configurations, each forming a directed forest of rooted trees.

A configuration is considered good if and only if it meets the following conditions:

• Any black point points to a white point,
• The product of the number of black points and white points in each cycle is even.

You need to calculate the number of good configurations, modulo the input modulus $P$.

Input Format

The input consists of a single line with three integers $n, m, P$, as described in the problem statement.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2 1 1000000

Sample Output #1

12

Sample Input #2

8 8 8888888

Sample Output #2

2973992

Sample Input #3

1000 1000 123456789

Sample Output #3

55105667

Notes

Sample 1 Explanation

Considering the restriction that black points must connect to white points, there are $3 \times 3 \times 2 = 18$ possible configurations, with one illegal configuration where a black point and a white point form a cycle. The number of ways to choose a white point and a black point to form a cycle is $2$, and the remaining white point has three options, thus the number of illegal configurations is $2 \times 3 = 6$, resulting in an answer of $18 - 6 = 12$.

Data Range and Constraints

For all test cases, $1 \le n, m \le 2000$, $1 \le P \le 10^9$.

Hints

You may need to consider the impact of constants on the efficiency of your algorithm.

Source

This problem is from the 2023 Tsinghua University Student Programming Contest and Invitational Tournament (THUPC2023) Finals.

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023.

见题面 Input 部分

见题面 Output 部分