Codeforces Global Round 24 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Doremy's Pegging Game

time limit per test

1.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputDoremy has $$$n+1$$$ pegs. There are $$$n$$$ red pegs arranged as vertices of a regular $$$n$$$-sided polygon, numbered from $$$1$$$ to $$$n$$$ in anti-clockwise order. There is also a blue peg of slightly smaller diameter in the middle of the polygon. A rubber band is stretched around the red pegs.

Doremy is very bored today and has decided to play a game. Initially, she has an empty array $$$a$$$. While the rubber band does not touch the blue peg, she will:

- choose $$$i$$$ ($$$1 \leq i \leq n$$$) such that the red peg $$$i$$$ has not been removed;
- remove the red peg $$$i$$$;
- append $$$i$$$ to the back of $$$a$$$.

Doremy wonders how many possible different arrays $$$a$$$ can be produced by the following process. Since the answer can be big, you are only required to output it modulo $$$p$$$. $$$p$$$ is guaranteed to be a prime number.

Input

The first line contains two integers $$$n$$$ and $$$p$$$ ($$$3 \leq n \leq 5000$$$, $$$10^8 \le p \le 10^9$$$) — the number of red pegs and the modulo respectively.

$$$p$$$ is guaranteed to be a prime number.

Output

Output a single integer, the number of different arrays $$$a$$$ that can be produced by the process described above modulo $$$p$$$.

Examples

Input

4 100000007

Output

16

Input

1145 141919831

Output

105242108

Note

In the first test case, $$$n=4$$$, some possible arrays $$$a$$$ that can be produced are $$$[4,2,3]$$$ and $$$[1,4]$$$. However, it is not possible for $$$a$$$ to be $$$[1]$$$ or $$$[1,4,3]$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 14:45:15 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|