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