Background

“In an ancient book, I once saw a Yin-Yang formation. It would surely help you conquer Kyushu. To use this formation, you must deploy various Yin and Yang generals. A Yin general is brave yet fierce; a Yang general is good at planning and is loyal and honest. In every Yin-Yang formation, each general must choose one general to connect to. There are also two rules you must remember well, and you must not weaken the formation: first, Yin supports Yin, which easily stirs emotions, so avoid it if possible; second, support and ring, the ring is the same for Yin and Yang, and it is defended with balance……”

Just as you were about to conquer Kyushu, you seemed to hear a familiar voice shouting in the distance: “No sleeping while working. You’ll be fired like this……” You finally came to your senses and found your XCPC teammate beside you, skillfully tightening screws, while several defective products had already slipped past on the assembly line. Nothing happened just now, you sighed, but……

Problem Description

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

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

In total there are $(n+m)^{n+m}$ possible configurations. Each configuration is a directed pseudoforest where each connected component is a directed cycle with in-trees attached (a directed functional graph).

A configuration is called good if and only if it satisfies the following conditions:

• Every black node points to a white node.
• For each directed cycle, the product of the number of black nodes and the number of white nodes on that cycle is even.

You need to count the number of good configurations among all configurations, modulo the input modulus $P$.

Input Format

One line with three integers $n, m, P$, with meanings as described in the statement.

Output Format

Output one line with one integer, the answer.

2 1 1000000

12

8 8 8888888

2973992

1000 1000 123456789

55105667

Hint

Sample 1 Explanation

Considering only the restriction that black nodes must point to white nodes, there are $3 \times 3 \times 2 = 18$ configurations in total. Any configuration where one black node and one white node form a cycle is invalid. The number of configurations where a chosen white node and a black node form a cycle is $2$. The remaining white node then has $3$ choices, so the number of invalid configurations is $2 \times 3 = 6$. Therefore, the answer is $18 - 6 = 12$.

Constraints

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

Hint

You may need to pay attention to the impact of constants on the efficiency of the algorithm.

Source

From the finals of the 2023 Tsinghua University Student Algorithmic Contest and Collegiate Invitational (THUPC2023).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5