New Year and Permutation
Contest: Hello 2020
Difficulty rating: 1600
Tags: combinatorics, math

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

Input format:
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).

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

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

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

Example input:
1 993244853

Example output:
1

Example input:
2 993244853

Example output:
6

Editorial:
By the definition of happiness, we are counting the number of tuples $$$(p, l, r)$$$ such that:
• $$$p$$$ is a permutation of length $$$n$$$
• $$$l, r$$$ is an integer with $$$1 \le l \le r \le n$$$
• $$$[l, r]$$$ is a framed subsegment in $$$p$$$
Instead of fixing the permutation $$$p$$$ as written in the statement, let's fix the integer $$$l, r$$$ and find the number of permutations of length $$$n$$$ with $$$[l, r]$$$ as a framed segment.
If $$$[l, r]$$$ is a framed subsegment, all numbers in the range $$$[min_{i = l}^{r} p_i, max_{i = l}^{r} p_i]$$$ belong exactly to the framed segment $$$[l, r]$$$. Thus, if we fix the order of numbers inside the segment, we can consider it as a single point, instead of a whole subsegment.
Let $$$len = r - l + 1$$$. We have $$$len!$$$ possible orders inside the segment. If we fix this order, the subsegment shrinks to a single number, and then we have to permute the $$$(n - len + 1)$$$ remaining numbers.
This gives the formula $$$(n - len + 1)! \times len!$$$ for subsegment $$$[l, r]$$$. If we precompute the factorial and add this value for all $$$1 \le l \le r \le n$$$, this can be calculated in $$$O(n^2)$$$ time. By observing that there exist exactly $$$n - len + 1$$$ pairs with $$$1 \le l \le r \le n, r - l + 1 = len$$$, we can simply multiply this number for each length, giving a $$$O(n)$$$ time solution.