Cntcrit

Task

You are given an integer $N$. Consider all the labeled undirected graphs with $N$ vertices. For each such graph, count the number of critical edges in it. Find the sum of the number of critical edges for all undirected graphs with $N$ vertices.

An edge $(u, v)$ is critical if by removing it, the number of connected components increases.

Since this number can be very large, print it modulo $M$, where $M$ is a prime number.

Input data

The first line of the input will contain the numbers $N$ and $M$.

Output data

Print a single integer, the sum of the number of critical edges for all undirected graphs with $N$ vertices.

Constraints and clarifications

• $1 \leq N \leq 5 \ 000$
• $2 \leq M \leq 10^{9} + 9$, $M$ is prime.

Example 1

stdin

6 2017

stdout

1254

Example 2

stdin

319 666013

stdout

385993