New Year and Permutation

题意翻译

1. 题目大意：在所有由[1，n]组成的排列中，有多少对数(l，r)满足max{pl，pl+1，…，pr} - min{pl，pl+1，…，pr} = r - l。 似乎解释的不是很清楚，再来个样例解释一下。 当n = 3时，所有的排列为[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]。 对于[1，2，3]：(1，1)中max = 1， min = 1， r - l = 0，成立；(1，3)中max = 3， min = 1， r - l = 2，成立。 对于[1，3，2]：(1，2)中max = 3， min = 1， r - l = 1，不成立。 别的懒得说了，原题样例说明有。

题目描述

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

输入输出样例

输入样例 #1

1 993244853

输出样例 #1

1

输入样例 #2

2 993244853

输出样例 #2

6

输入样例 #3

3 993244853

输出样例 #3

32

输入样例 #4

2019 993244853

输出样例 #4

923958830

输入样例 #5

2020 437122297

输出样例 #5

265955509

说明

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