Problem Description

Chino wants to create a mock competition using the $n$ problems she currently has. Initially, these $n$ problems are arranged in order of increasing difficulty.

However, because Chino is a cute girl, she will shuffle the order of these problems. Specifically, she will perform an odd number of operations, each involving swapping the positions of two problems. A possible mock competition is a permutation of these problems.

To evaluate the cuteness level of a mock competition, Chino defines $s$ as the minimum number of operations required to transform the initial order into the order of the mock competition, and $t$ as the number of problems that remain in their original positions in the mock competition. The cuteness level of the mock competition is then defined as $s/(t+1)$.

Following the usual routine, you are now tasked with helping Chino calculate the cuteness level of a specific mock competition. Chino finds this insufficiently cute, so she wants you to calculate twice the sum of the cuteness levels of all possible mock competitions. It can be noted that this is always a non-negative integer. To avoid excessively large answers, you only need to output the result modulo a prime number $p$.

Formally, for a permutation $\pi$, let $\nu(\pi)$ denote the number of fixed points, and $\upsilon(\pi)$ denote the minimum number of transpositions needed to decompose $\pi$. Let $S_n$ be the symmetric group on $n$ elements and $A_n$ be the alternating group on $n$ elements. Compute
$$ 2\sum_{\pi\in S_n\land\pi\notin A_n}\frac{\upsilon(\pi)}{\nu(\pi)+1}. $$

This is always a non-negative integer. Output the result modulo the prime number $p$.

Input Format

The input consists of a single line containing two positive integers $n$ and $p$.

Output Format

Output a single non-negative integer, which is the result of the sum of the cuteness levels of all possible mock competitions modulo $p$.

Sample Input and Output

Sample Input #1

4 16777259

Sample Output #1

40

Sample Input #2

10 2147483647

Sample Output #2

17167120

Sample Input #3

10000000 998244353

Sample Output #3

3414058

Notes/Hints

Sample Explanation #1

All possible permutations of the four problems and their cuteness levels are:
- $\{1,2,4,3\}$, cuteness level is $1/3$;
- $\{1,3,2,4\}$, cuteness level is $1/3$;
- $\{1,4,3,2\}$, cuteness level is $1/3$;
- $\{2,1,3,4\}$, cuteness level is $1/3$;
- $\{2,3,4,1\}$, cuteness level is $3$;
- $\{2,4,1,3\}$, cuteness level is $3$;
- $\{3,1,4,2\}$, cuteness level is $3$;
- $\{3,2,1,4\}$, cuteness level is $1/3$;
- $\{3,4,2,1\}$, cuteness level is $3$;
- $\{4,1,2,3\}$, cuteness level is $3$;
- $\{4,2,3,1\}$, cuteness level is $1/3$;
- $\{4,3,1,2\}$, cuteness level is $3$.

Test Case Constraints

This problem uses subtask-based scoring.

For all data, $1 \leq n \leq 2 \times 10^7$ and $2^{25} < p < 2^{31}$, where $p$ is a prime number.

The specific constraints for each subtask are as follows:

Faster Modulo Operation

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

见题面 Input 部分

见题面 Output 部分