P9419 [POI 2021/2022 R1] Arranging Cards

Translated from [XXIX Olimpiada Informatyczna – Stage I](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Układanie kart](https://sio2.mimuw.edu.pl/c/oi29-1/p/ukl/)。

We sort a permutation into increasing order using the following method. One operation: Let the first number be $k$. Find $k-1$ in the permutation (if $k=1$, take $n$). Move $k-1$ to the first position of the permutation, and shift the numbers in between one position to the right. Cost of one operation: the position of $k-1$ (or $n$) in the original permutation (indexed starting from $0$). Cost of a permutation: perform several operations until the permutation is sorted. The cost is the sum of the costs of all operations. Given $n,m$, find the sum of the costs over all $n!$ permutations, modulo $m$.

One line with two positive integers, $n,m$.

One line with one integer, the answer modulo $m$.

For all testdata, $2\leq n\leq 1000000$，$2\leq m\leq 10^9$。 | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n\leq 10$ | 10 | | 2 | $n\leq 2000$ | 60 | | 3 | | 30 | Translated by ChatGPT 5