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

回忆一下，排列是指由 $1$ 到 $n$ 的 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

若序列 $a$ 可通过从序列 $b$ 的开头删除若干（可能为零个或全部）元素、并从结尾删除若干（可能为零个或全部）元素而得到，则称 $a$ 是 $b$ 的一个子段。我们将子段记作 $[l, r]$，其中 $l, r$ 是满足 $1 \le l \le r \le n$ 的两个整数，表示从原序列中删去开头的 $l-1$ 个元素和结尾的 $n-r$ 个元素后所剩下的部分。

对于一个排列 $p_1, p_2, \ldots, p_n$，我们定义一个带框子段（framed segment） 为满足如下条件的子段 $[l,r]$：

$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l.$$

例如，对排列 $(6, 7, 1, 8, 5, 3, 2, 4)$，其部分带框子段包括：$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$。特别地，对任意 $i$（$1 \le i \le n$），单元素子段 $[i,i]$ 总是一个带框子段。

我们定义一个排列 $p$ 的幸福值（happiness） 为满足 $1 \le l \le r \le n$ 且 $[l, r]$ 是带框子段的数对 $(l, r)$ 的个数。例如，排列 $[3, 1, 2]$ 的幸福值为 $5$：除子段 $[1, 2]$ 外，其余所有子段均为带框子段。

给定整数 $n$ 和 $m$，Jongwon 希望计算所有长度为 $n$ 的排列的幸福值之和，并对素数 $m$ 取模。注意：长度为 $n$ 的不同排列共有 $n!$（$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).

唯一一行包含两个整数 $n$ 和 $m$（$1 \le n \le 250\,000$，$10^8 \le m \le 10^9$，且 $m$ 为质数）。

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

输出 $r$（$0 \le r \lt m$），即所有长度为 $n$ 的排列的幸福值之和对素数 $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$.

对于样例输入 $n=3$，我们考虑所有长度为 $3$ 的排列：

• $[1, 2, 3]$，所有子段均为“框定子段”（framed segment）。幸福值为 $6$。
• $[1, 3, 2]$，除子段 $[1, 2]$ 外，其余所有子段均为“框定子段”。幸福值为 $5$。
• $[2, 1, 3]$，除子段 $[2, 3]$ 外，其余所有子段均为“框定子段”。幸福值为 $5$。
• $[2, 3, 1]$，除子段 $[2, 3]$ 外，其余所有子段均为“框定子段”。幸福值为 $5$。
• $[3, 1, 2]$，除子段 $[1, 2]$ 外，其余所有子段均为“框定子段”。幸福值为 $5$。
• $[3, 2, 1]$，所有子段均为“框定子段”。幸福值为 $6$。

因此，幸福值总和为 $6+5+5+5+5+6 = 32$。