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