23714번 - Lidia Perovskaya 다국어

$n$ players are playing in an elimination tournament. The tournament is a sequence of $n - 1$ matches. Each match consists of two people playing against each other. One of them loses and is eliminated from the tournament (i.e. he can't participate in any further matches) and the other one wins and is not eliminated. The last match is called the final, because it consists of the only two not eliminated players. No two consecutive matches, none of which is the final, may share a participant.

How many different possible tournaments are there? Two tournaments are considered different if there exists a pair of players which played against each other in one of them but didn't in the other.

Output the correct answer modulo a prime number $m$. Formally, if the actual answer is $y$ and your answer is $x$, it will be considered correct if $-2^{63} \leq x < 2^{63}$ and $x-y$ is divisible by $m$.

The only line contains two integers $n$ and $m$ ($2 \leq n \leq 10^6, 10^6 + 3  \leq m \leq 10^9+9$, $m$ is prime), the number of players and the modulo.

Print a single integer --- the number of possible tournaments modulo $m$.