KONGJUNE / / ACM / 阅读量

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≤l≤r≤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,…,p_n$, we define a framed segment as a subsegment $[l,r]$ where $\max{p_l,p_{l+1},…,p_r}−\min{p_l,p_{l+1},…,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≤l≤r≤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$.

### Input

The only line contains two integers $n$ and $m$ ($1≤n≤250000$, $108≤m≤109$, $m$ is prime).

### Output

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

### Examples

Input Output
1 993244853 1
2 993244853 6
3 993244853 32
2019 993244853 923958830
2020 437122297 265355509

### Note

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

• 当子序列长度为 $1$ 时，序列的每一个子序列都是符合条件的，而序列的排列数共有 $n!$ 种，故这种情况下，幸福度(happiness)为 $n \cdot n!$。

• 当子序列长度为 $2$ 时，我们有以下分析:

序列共有 $n!$ 种，每个序列均有 $n - 1$ 个不同的长度为 $2$ 的子序列。而这些子序列是随机出现的，所以他们成为符合条件的子序列的概率相等。

至于子序列符合条件的概率，我们现在只考虑长度为 $2$ 的子序列。

长度为 $2$ 的子序列共有 $A_n^2 = n(n-1)$ 种，其中满足条件的有 $(n - 1) \cdot 2!$ 种，即不考虑顺序的从序列 $1,2,3,\dots,n$ 种连续选择长度为 $2$ 的子序列有 $n - 1$ 种，再考虑每个序列的顺序有 $2!$ 种。所以满足条件的概率为 $\frac{(n-1)\cdot2!}{A_n^2}$ 。

综上，长度为 $2$ 的子序列的幸福度(happiness)的总和为 $n!(n - 1) \cdot \frac{(n - 1) \cdot 2!}{A_n^2}$。

• 当子序列长度为 $3$ 时，根据类似的分析，我们得到的幸福度总和为 $n!(n - 2)\cdot\frac{(n - 2)\cdot3!}{A_n^3}$。

$$\sum_{i =1}^n(n - i + 1)\cdot i ! \cdot(n - i + 1)!$$

• $(a+b) \mod p = (a \mod p + b\mod p)\mod p$

• $(a-b)\mod p =(a\mod p - b \mod p)\mod p$

• $(a\times b) \mod p =(a\mod p\times b \mod p) \mod p$

• $(a ^ b)\mod p = ((a \mod p) ^ b)\mod p$

• 除法：分子乘以分母的乘法逆元。

$(a\div b)\mod p = (a\times b^{p - 2} )\mod p$

AC代码：

#include <bits/stdc++.h>
using namespace std;
long long mul[250005];
int main() {
int n, m;
cin >> n >> m;
mul[0] = 1;
for (int i = 1; i <= n; i++) {
mul[i] = ((mul[i - 1] % m) * (i % m)) % m;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + ((((n - i + 1) % m) * ((mul[i] * mul[n - i + 1]) % m)) % m)) % m;
}
cout << ans << endl;
}