34790번 - Pair Linked Mokepon 다국어

문제

The popular game of Mokepon can be represented as a list of $n$ stations with special items located at them and a player beginning at station 1ドル$. Each item has an identifier id (2ドル\le$id$\le n$) (and no two items may have the same identifier), and the player is required to have the item with identifier $i$ to be able to move to station $i$ from station $i - 1$. Stations may have multiple (including none) items, and the player can pick up and hold an unlimited number of items. The objective is to reach the last station: station $n$.

You and your friend find this game too easy, so you decide to link up two games of Mokepon: your game has $n_{\text{A}}$ stations and your friend's game has $n_{\text{B}}$ stations. However, special items may appear in either game, and are now uniquely identified by the pair of $($id,ドル \text{A or B})$: its identifier, and which game it comes from. To progress to station $i$ in a given game, either one of you must have picked up the item with identifier $i$ for that game.

The games randomize where items gets placed in each of the game, and so not every placement of items may be possible to win from. Your goal is to count the number of distributions of items such that it is possible for the two of you to both reach the end station in your respective games. Since this number may be large, calculate it modulo a prime $p$.

We say two distributions of items to stations are different if there is at least one station where the set of items at that station differ.

입력

The only line of input contains three integers, $n_\text{A},ドル $n_\text{B},ドル and $p$ ( 2ドル\le n_\text{A}, n_\text{B}\le 3\cdot 10^3,ドル 10ドル^8\le p\le 10^9 + 7$) --- the number of stations in your and your friend's game, respectively, and the modulo to calculate with respect to.

It is guaranteed that $p$ is a prime.

출력

Output a single integer, the number of distributions of items such that both players win their respective games, modulo $p$.

제한

노트

In the first sample, there are two special items: $(2, \text{A})$ and $(2, \text{B})$ corresponding to the two games $\text{A}$ and $\text{B}$ respectively, and thus 4ドル^2 = 16$ configurations of stations where they could be located. The eight winning possibilities (in the notation (station, game)) are listed below, along with illustrations of the first two possibilities.

• $(1, A)$; $(1, A)$: Both players can immediately progress to their respective end stations.
• $(1, A)$; $(2, A)$: The first player unlocks their final station, at which point the second player can progress.
• $(1, A)$; $(1, B)$
• $(1, B)$; $(1, A)$
• $(1, B)$; $(1, B)$
• $(1, B)$; $(2, A)$
• $(2, B)$; $(1, A)$
• $(2, B)$; $(1, B)$