CF1284C New Year and Permutation

我们称排列为一个由 $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）为满足 $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$ 的子段 $[l, r]$。例如，对于排列 $(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$ 的“幸福值”为满足 $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$ 和 $m$（$1 \le n \le 250\,000$，$10^8 \le m \le 10^9$，$m$ 为质数）。

输出一个整数 $r$（$0 \le r < m$），表示所有长度为 $n$ 的排列的幸福值之和，对质数 $m$ 取模后的结果。

对于样例输入 $n=3$，我们考虑所有长度为 $3$ 的排列： - $[1, 2, 3]$，所有子段都是框定段。幸福值为 $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$。 由 ChatGPT 4.1 翻译