Cute Simulation Contest

Chino wants to design a simulation contest using the $n$ problems she currently has. Initially the problems are arranged in increasing order of difficulty. However, since Chino is an adorable girl, she shuffles the problems by performing an odd number of operations where in each operation two problems swap positions. Such a permutation of the $n$ problems represents one possible simulation contest.

To measure the cuteness of a contest, she defines two quantities for a permutation $\pi$:

• $s=\upsilon(\pi)$: the minimum number of transpositions required to transform the initial order into $\pi$. It is well known that $\upsilon(\pi)= n- c(\pi)$, where $c(\pi)$ is the number of cycles in $\pi$.
• $t=\nu(\pi)$: the number of fixed points in $\pi$.

The cuteness of the contest is defined as

$$\frac{s}{t+1} = \frac{n-c(\pi)}{\nu(\pi)+1}.$$

Since Chino thinks that one contest is not cute enough, she asks you to compute the following sum modulo a prime number $p$:

$$2\sum_{\substack{\pi\in S_n\\\pi\notin A_n}} \frac{\upsilon(\pi)}{\nu(\pi)+1} = 2\sum_{\substack{\pi\in S_n\\\pi\notin A_n}} \frac{n-c(\pi)}{\nu(\pi)+1}, $$

where $S_n$ is the symmetric group of $n$ elements and $A_n$ is the alternating group of even permutations. Note that for any permutation $\pi$, its sign is given by

$$\mathrm{sgn}(\pi)=(-1)^{n-c(\pi)}.$$

Thus, only the odd permutations (i.e. those with $n-c(\pi)$ odd) contribute to the sum. It can be shown that the final answer is a nonnegative integer. Your task is to output the answer modulo $p$.

inputFormat

The input consists of a single line containing two integers $n$ and $p$, where $n$ is the number of problems and $p$ is a prime number.

\(1 \le n \le 12\) (for this problem, $n$ is small enough so that a combinatorial enumeration is feasible) and $p$ is a prime number.

outputFormat

Output a single integer: the value of

$$2\sum_{\substack{\pi\in S_n\\\pi\notin A_n}} \frac{n-c(\pi)}{\nu(\pi)+1} \mod p. $$

sample

1 7

0