Description

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 Format

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

Output Format

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$.

4 16777259

40

10 2147483647

17167120

10000000 998244353

3414058

Hint

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}<p<2^{31}$, and $p$ is a prime.

The detailed limits of each subtask are shown in the table below:

Subtask ID	Score	$n\le$	$p=998244353$
1	10	$2\times10^1$	$\times$
2		$2\times10^2$	$\surd$
3		$2\times10^3$	$\times$
4	20	$2\times10^4$
5		$2\times10^5$	$\surd$
6	10	$2\times10^6$
7	20	$2\times10^7$	$\times$

Faster Modulo

In this problem, you may perform a large number of modulo operations. Therefore, you can refer to several modulo optimization methods (translated from min-25's blog) to improve the efficiency of modulo operations.

Translated by ChatGPT 5