P7120 Chino's Contest.

Chino wants to use the $n$ problems she currently has to create a mock contest. At the beginning, these $n$ problems are arranged from easy to hard. However, because Chino is a cute girl, she will shuffle the order of these problems. Specifically, she will perform exactly an odd number of operations, and in each operation she swaps the positions of two problems. A possible mock contest is a permutation of these problems. To evaluate how cute a mock contest is, Chino defines $s$ as the minimum number of operations needed to change the initial order into the order of this mock contest, and defines $t$ as the number of problems that stay in the same position in both the initial order and this mock contest. Then the cuteness of this mock contest is $s/\left(t+1\right)$. As usual, you are now supposed to help Chino compute the cuteness of one mock contest. Chino thinks this is not cute enough, so she wants you to compute twice the sum of the cuteness over all possible mock contests. It can be shown that this is always a non-negative integer. To avoid the answer being too large, you only need to output it modulo the prime $p$. Formally, for a permutation $\pi$, let $\nu\left(\pi\right)$ denote its number of fixed points, and let $\upsilon\left(\pi\right)$ be the minimum number of transpositions in a decomposition of $\pi$ into a product of transpositions. Let the symmetric group on $n$ elements be $S_n$, and the alternating group on $n$ elements be $A_n$. Compute $$ 2\sum_{\pi\in S_n\land\pi\notin A_n}\frac{\upsilon\left(\pi\right)}{\nu\left(\pi\right)+1}. $$ This is guaranteed to be a non-negative integer. Output the answer modulo the prime $p$.

Input one line with two positive integers $n,p$.

Output one line with one non-negative integer, which is the sum of the cuteness over all possible mock contests of $n$ problems, modulo $p$.

### Sample Explanation #1 All possible mock contest permutations of four problems are: - $\left\{1,2,4,3\right\}$, with cuteness $1/3$; - $\left\{1,3,2,4\right\}$, with cuteness $1/3$; - $\left\{1,4,3,2\right\}$, with cuteness $1/3$; - $\left\{2,1,3,4\right\}$, with cuteness $1/3$; - $\left\{2,3,4,1\right\}$, with cuteness $3$; - $\left\{2,4,1,3\right\}$, with cuteness $3$; - $\left\{3,1,4,2\right\}$, with cuteness $3$; - $\left\{3,2,1,4\right\}$, with cuteness $1/3$; - $\left\{3,4,2,1\right\}$, with cuteness $3$; - $\left\{4,1,2,3\right\}$, with cuteness $3$; - $\left\{4,2,3,1\right\}$, with cuteness $1/3$; - $\left\{4,3,1,2\right\}$, with cuteness $3$. ### Constraints **This problem uses bundled testdata.** For all data, $1\le n\le2\times10^7$, $2^{25}