A13072. New Year and Permutation

Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $[l, r]$ , where $l, r$ are two integers with $1 \le l \le r \le n$ . This indicates the subsegment where $l-1$ elements from the beginning and $n-r$ elements from the end are deleted from the sequence.

For a permutation $p_1, p_2, \ldots, p_n$ , we define a framed segment as a subsegment $[l,r]$ where $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$ . For example, for the permutation $(6, 7, 1, 8, 5, 3, 2, 4)$ some of its framed segments are: $[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$ . In particular, a subsegment $[i,i]$ is always a framed segments for any $i$ between $1$ and $n$ , inclusive.

We define the happiness of a permutation $p$ as the number of pairs $(l, r)$ such that $1 \le l \le r \le n$ , and $[l, r]$ is a framed segment. For example, the permutation $[3, 1, 2]$ has happiness $5$ : all segments except $[1, 2]$ are framed segments.

Given integers $n$ and $m$ , Jongwon wants to compute the sum of happiness for all permutations of length $n$ , modulo the prime number $m$ . Note that there exist $n!$ (factorial of $n$ ) different permutations of length $n$ .

The only line contains two integers $n$ and $m$ ( $1 \le n \le 250\,000$ , $10^8 \le m \le 10^9$ , $m$ is prime).

Print $r$ ( $0 \le r < m$ ), the sum of happiness for all permutations of length $n$ , modulo a prime number $m$ .

For sample input $n=3$ , let's consider all permutations of length $3$ :

- $[1, 2, 3]$ , all subsegments are framed segment. Happiness is $6$ .
- $[1, 3, 2]$ , all subsegments except $[1, 2]$ are framed segment. Happiness is $5$ .
- $[2, 1, 3]$ , all subsegments except $[2, 3]$ are framed segment. Happiness is $5$ .
- $[2, 3, 1]$ , all subsegments except $[2, 3]$ are framed segment. Happiness is $5$ .
- $[3, 1, 2]$ , all subsegments except $[1, 2]$ are framed segment. Happiness is $5$ .
- $[3, 2, 1]$ , all subsegments are framed segment. Happiness is $6$ .

Thus, the sum of happiness is $6+5+5+5+5+6 = 32$ .