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

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